分析根据题目所说要统计雨水的体积实际是统计雨水的面积要考虑到左右两边柱子的高低。实例1输入height [0,1,0,2,1,0,1,3,2,1,2,1]输出6解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。题解暴力对于下标i ii的柱子这个位置能接住的雨水高度 左右两侧最高柱子中较矮的那一根高度 - 当前柱子高度val min(leftMax, rightMax) - height[i]如果v a l 0 val 0val0可以积水加上该水量如果v a l ≤ 0 val \le 0val≤0当前柱子高于两侧矮边的最大值存不住水积水为0。代码classSolution{public:inttrap(vectorintheight){intres0;intnheight.size();for(inti1;in-1;i){intlmax0,rmax0;for(intj0;ji;j)lmaxmax(lmax,height[j]);for(intji1;jn;j)rmaxmax(rmax,height[j]);intvalmin(lmax,rmax)-height[i];if(val0)resarea;}returnres;}};时间复杂度O ( n 2 ) O(n^2)O(n2)提交到力扣上面会超时所以要采用一下解法。双指针双指针用两个变量动态保存左侧历史最大值lMax、右侧历史最大值rMax。规则左指针l在最左、右指针r在最右哪边柱子高度更小哪边就是决定水位的短板只处理这一侧若height[l] height[r]水位由左侧最高墙lMax决定若height[r] height[l]水位由右侧最高墙rMax决定当前柱子高度≥ \ge≥历史最高墙存不住水更新最高墙当前柱子高度 \lt历史最高墙可以蓄水累加水量。左右指针同时起到遍历的作用。代码classSolution{public:inttrap(vectorintheight){intl0,rheight.size()-1;intlMax0,rMax0;intres0;while(lr){if(height[l]height[r]){if(height[l]lMax)lMaxheight[l];elsereslMax-height[l];l;}else{if(height[r]rMax)rMaxheight[r];elseresrMax-height[r];r--;}}returnres;}};时间复杂度O ( n ) O(n)O(n)DPDP 核心思想单个位置i ii蓄水量公式water[i] min(leftMax[i], rightMax[i]) - height[i]leftMax[i]下标i ii左侧所有柱子的最大高度包含i iirightMax[i]下标i ii右侧所有柱子的最大高度包含i iiDP做法分三步正向遍历数组算出leftMax[]反向遍历数组算出rightMax[]遍历每个位置通用公式累加雨水。递推公式l e f t M a x [ i ] m a x ( l e f t M a x [ i − 1 ] , h e i g h t [ i ] ) leftMax[i] max(leftMax[i-1], height[i])leftMax[i]max(leftMax[i−1],height[i])r i g h t M a x [ i ] m a x ( r i g h t M a x [ i 1 ] , h e i g h t [ i ] ) rightMax[i] max(rightMax[i1], height[i])rightMax[i]max(rightMax[i1],height[i])代码classSolution{public:inttrap(vectorintheight){intnheight.size();if(n0)return0;vectorintleftMax(n),rightMax(n);leftMax[0]height[0];for(inti1;in;i)leftMax[i]max(leftMax[i-1],height[i]);rightMax[n-1]height[n-1];for(intin-2;i0;i--)rightMax[i]max(rightMax[i1],height[i]);intres0;for(inti0;in;i)resmin(leftMax[i],rightMax[i])-height[i];returnres;}};时间复杂度O ( n ) O(n)O(n)这是典型的空间换时间。单调栈前面DP、双指针都是竖着算对每个位置看上下能存多高的水。单调栈是横着算一层一层横向计算凹槽的积水面积。栈中存放柱子下标维持规则栈内对应的高度严格递减。一旦遇到一根更高的柱子说明形成了凹槽可以借助雨水弹出栈顶作为凹槽底部计算积水宽度与高度。积水计算公式弹出凹槽底部下标bottom后栈不为空左边界 栈顶下标left右边界 当前下标i积水宽度width i - left - 1积水高度h min(height[left], height[i]) - height[bottom]本次积水体积width * h代码classSolution{public:inttrap(vectorintheight){stackintst;intres0;intnheight.size();for(inti0;in;i){while(!st.empty()height[i]height[st.top()]){intbottomst.top();st.pop();if(st.empty())break;intleftst.top();intwidthi-left-1;inthmin(height[left],height[i])-height[bottom];reswidth*h;}st.push(i);}returnres;}};1.为什么栈存下标而不是高度既要拿到高度比较大小又要用下标计算凹槽的宽度。2.弹出元素后栈为空就break凹槽必须左右都有围墙才能存水。如果弹出底部后栈空左边没有围墙无法蓄水。3.栈始终保持递减只有更高的柱子到来时才结算积水符合”两边高、中间低才能存水“的物理规则。时间复杂度O ( n ) O(n)O(n)每个下标只会入栈一次、出栈一次空间复杂度O ( n ) O(n)O(n)最坏情况严格递减数组所有元素进栈。总结上述题解的核心都是val min(leftMax, rightMax) - height[i]四种方法对比解法计算方式时间空间特点暴力纵向逐点遍历O ( n 2 ) O(n^2)O(n2)O ( 1 ) O(1)O(1)最简单会超时双指针纵向、双指针动态维护最值O ( n ) O(n)O(n)O ( 1 ) O(1)O(1)最优面试推荐DP纵向、预处理左右最大数组O ( n ) O(n)O(n)O ( n ) O(n)O(n)易懂空间换时间单调栈横向逐层计算积水O ( n ) O(n)O(n)O ( n ) O(n)O(n)单调栈经典题型42. 接雨水 - 力扣LeetCode