Leetcode - 42 接雨水（一维）

原题链接分析首先分析题目给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。n height.length1 n 2 * 1040 height[i] 105也就是计算所有接到的雨水的数量。先竖着看每次计算一个位置可以保存的雨水也可以横着看每次计算一小横行可以存储多少雨水。1 竖着看竖着看一个位置存储的雨水就取决于左右两侧柱子的较小值。所以只需要计算每个位置左右两侧最大值然后取出较小值计算就可以了。那么就使用数组存储就可以时间复杂度O(n) 空间复杂度On。还可以进一步优化优化空间复杂度到O1也就是不提前存储而是直接每次计算。使用双指针同时使用两个数值记录当前左右两侧最高值。由于每个位置能够存储的水和两侧最高柱子的较小值有关。那么对于左指针如果左侧最高值小于右侧也就是右侧一定更高右侧可能还有更高的柱子左侧就是当前确定最大值两侧中较小值一定是左侧的。那么就可以计算出这个位置可以存储的水量。右侧反之同理。例如当前位置l1,r11,lmax1,rmax2这里表示高度那么就可以确定当前 l 位置存储的水量。代码classSolution{public:inttrap(vectorintheight){intnheight.size();intl0;intrn-1;longlongans0;intlm0;intrm0;while(lr){lmmax(lm,height[l]);rmmax(rm,height[r]);if(lmrm){anslm-height[l];}else{ansrm-height[r--];}}returnans;}};横着看首先注意到如果能够存储水柱子的结构应该是凹形的。使用单调栈栈底到栈顶存储的柱子高度应该逐渐下降。每次如果遍历的柱子比栈顶高就说明当前形成了一个凹形区域可以计算当前部分的存储水量如下代码classSolution{public:inttrap(vectorintheight){intnheight.size();stackints;longlongans0;for(inti0;in;i){while(!s.empty()height[i]height[s.top()]){intms.top();s.pop();if(s.empty()){break;}intls.top();ans(i-l-1)*(min(height[i],height[l])-height[m]);}s.push(i);}returnans;}};