本文共 2162 字，大约阅读时间需要 7 分钟。
思路一：单独考虑每一个位置 i i i，假设在 [ 0 , i − 1 ] [0,i-1] [0,i−1]内的最大值为 m a x l maxl maxl，在 [ i + 1 , n − 1 ] [i+1,n-1] [i+1,n−1]内的最大值为 m a x r maxr maxr，则位置 i i i的存水量等于 m a x ( h e i g h t [ i ] , m i n ( m a x l , m a x r ) ) − h e i g h t [ i ] max(height[i],min(maxl,maxr))-height[i] max(height[i],min(maxl,maxr))−height[i]。那么遍历两边即可求出结果。 class Solution { public: int trap(vector & height) { int siz=height.size(); if(!siz) return 0; vector maxarr(siz); int MAX=0; for(int i=0;i =0;i--){ tmp=min(MAX,maxarr[i]); if(tmp>height[i]) ans+=tmp-height[i]; MAX=max(MAX,height[i]); } return ans; }}; 思路二：双指针。这个思路相当于思路一的反向思维。思路一是对于每个位置，确定左边界和右边界，然后计算贡献。思路二是先确定左右边界，再统计位置的贡献。搞两个指针， l l l从左向右扫， r r r从右向左扫，不妨假设 h e i g h t [ l ] < = h e i g h t [ r ] height[l]<=height[r] height[l]<=height[r]，那么对于从 l l l开始的单调递减区间内的每一个值 v v v，对答案都有 h e i g h t [ l ] − v height[l]-v height[l]−v的贡献；如果 h e i g h t [ l ] > h e i g h t [ r ] height[l]>height[r] height[l]>height[r]，那么类似的从 r r r开始想左扫就好了。如果不存在这样的区间的话，说明这个位置不能产生贡献，移动指针选定下一对左右边界即可。
class Solution { public: int trap(vector & height) { int siz=height.size(); int l=0,r=siz-1,ans=0; while(l l&&height[r] 思路三：单调栈，比较难想到。和思路二有一点点像。想象一下，我们维护了一个单调递减的栈，假设当前右侧边界高度为 h 1 h_1 h1，栈顶高度为 h 2 h_2 h2，栈顶的下一个元素的高度为 h 3 h_3 h3，那么只要 h 1 > h 2 h_1>h_2 h1>h2，就可以以 h 2 h_2 h2为底， h 1 h_1 h1为右边界， h 3 h_3 h3为左边界，把中间这一块填满。详见代码，可以自己画图理解一下。
class Solution { public: int trap(vector & height) { //单调栈 但是存储的是下标 stack s; int ans=0,siz=height.size(); for(int i=0;i =height[tmp=s.top()]){ s.pop(); if(!s.empty()){ //s.top为左边界 tmp为底 i为右边界 //MIN-height[tmp] 为填充的区块的高度 //i-s.top-1 为填充的区块的宽度 int MIN=min(height[s.top()],height[i]); ans+=(MIN-height[tmp])*(i-s.top()-1); } } s.push(i); } return ans; }}; 转载地址：https://blog.csdn.net/xiji333/article/details/107944320 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
