1574. 接雨水 AcWing
标签：mes names content 指针 方便 pre space ble 思路
原题链接
单调栈：
如果有凹陷处,那么雨水=左边的第一个单调上升最大的与右边单调上升最大的取最小值与当前高度做差,思路很像单调栈,我们需要找到凹陷处,即需要用栈吞入比当前栈
顶小的值,如果遇到比它的值就停下,存储当前栈顶下标(方便计算宽度),这是按行计算的,当计算完毕后,不能将左边的圆柱pop,因为我们还需要计算以它为底作雨水容器的体积,当栈空或者拿比右边的圆柱还大的圆柱作底就停下来.最后要将右圆柱入栈
1 #include 2 using namespace std;
3 int h[100010];
4 stackint> s;
5 int main()
6 {
7 // freopen("in.txt","r",stdin);
8 int n,sum = 0;
9 scanf("%d",&n);
10 for(int i=1;i){
11 scanf("%d",&h[i]);
12 if(s.empty()||h[i]continue;}
13 while(!s.empty()&&h[s.top()]h[i]){
14 int t = s.top();
15 s.pop();
16 if(s.empty()) break;
17 int wid = i-s.top()-1;
18 sum+=(min(h[i],h[s.top()])-h[t])*wid;
19 }
20 s.push(i);
21 }
22 printf("%d\n",sum);
23 }
单调栈
双指针:
指针移动需要让小的指针先移动,这样才能逼近最大的圆柱,边走变更新最值,只有当从高处到低处的时候,我们才需要+ans
1 #include 2 using namespace std;
3 const int N = 1e5+10;
4 int l[N],r[N],h[N],ans;
5 int main()
6 {
7 int n;
8 scanf("%d",&n);
9 for(int i=1;i"%d",&h[i]);
10 int left = 0,right = n,lmax = h[0],rmax = h[n];//让小的先移动逼近最大值
11 while(leftright){
12 lmax = max(h[left],lmax);
13 rmax = max(h[right],rmax);
14 if(lmaxrmax){
15 ans += lmax-h[left];
16 left++;
17 }else{
18 ans += rmax-h[right];
19 right--;
20 }
21 }
22 printf("%d\n",ans);
23 }
双指针
1574. 接雨水 AcWing
标签：mes names content 指针 方便 pre space ble 思路
原文地址：https://www.cnblogs.com/ndfwblog/p/14164460.html
评论