接雨水C++
2022/3/28 11:22:34
本文主要是介绍接雨水C++,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)
#include<iostream> #include<vector> using namespace std; int main() { int n; char c; int sum1=0; vector<int>x, a;//x存储数,a存储进栈的下标 int maa; while(scanf("%d",&n)) { x.push_back(n); c = getchar(); if (c == '\n')break; } vector<int> result(x); for(int i=0;i<x.size();++i) { while (!a.empty()&&x[a.back()]<x[i])//单减; { maa = 0; n = a.back();//记录位置 a.pop_back();//此时栈顶为上一个比他大的数字位置; if (!empty(a)) { maa = min(x[a.back()], x[i]); for (int j = a.back() + 1; j < i; ++j)x[j] = maa; } //if (empty(a))result[n] = i * x[n]; } a.push_back(i); } //for (int i = 0; i < result.size(); ++i)cout << result[i]<<" "; for (int i = 0; i < result.size(); ++i)sum1+=(x[i]-result[i]); cout << sum1; return 0; }//1 1 2 1 3 0 2 0 5 0 4 0 1 1 2:16
注意对单调栈的理解,即以O(n)的速度得知每个元素的左右各两边第一个比他(小)大的位置上;
这篇关于接雨水C++的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain