LeetCode.42 接雨水题目描述给定n个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。示例输入height [0,1,0,2,1,0,1,3,2,1,2,1] 输出6方法一前缀最大值 后缀最大值动态规划思路分析对于每一个位置i它能接的雨水量取决于它左边最高的柱子和右边最高的柱子中较矮的那一个木桶效应。即water[i] min(左边最高, 右边最高) - height[i]如果这个差值为负则取 0。我们可以预先计算两个数组pre_max[i]表示从下标 0 到 i 的最大高度前缀最大值。suf_max[i]表示从下标 i 到 n-1 的最大高度后缀最大值。然后遍历每个位置累加min(pre_max[i], suf_max[i]) - height[i]即可。代码实现classSolution{public:inttrap(vectorintheight){intnheight.size();vectorintpre_max(n);pre_max[0]height[0];for(inti1;in;i)pre_max[i]max(pre_max[i-1],height[i]);vectorintsuf_max(n);suf_max[n-1]height[n-1];for(intin-2;i0;--i)suf_max[i]max(suf_max[i1],height[i]);intans0;for(inti0;in;i)ansmin(pre_max[i],suf_max[i])-height[i];returnans;}};复杂度分析时间复杂度O(n)遍历三次数组。空间复杂度O(n)使用了两个辅助数组。方法二双指针思路分析方法一需要额外 O(n) 的空间实际上我们可以用两个指针和两个变量在遍历过程中动态维护左右两侧的最大高度将空间优化到 O(1)。核心思想用left和right指针分别指向数组的两端并维护pre_max和suf_max分别表示[0, left]的最大值和[right, n-1]的最大值。在每一轮中比较pre_max和suf_max如果pre_max suf_max则对于left位置它的右侧最大高度至少为suf_max因此该位置的积水高度由pre_max决定累加pre_max - height[left]并右移left。否则对称处理right位置。为什么这样正确因为当pre_max suf_max时left位置的右侧最大高度一定 ≥suf_maxpre_max所以min(左侧最大, 右侧最大) pre_max该位置接水量确定。移动指针后新的pre_max或suf_max会更新继续处理下一个位置。代码实现classSolution{public:inttrap(vectorintheight){intans0,pre_max0,suf_max0;intleft0,rightheight.size()-1;while(leftright){pre_maxmax(pre_max,height[left]);suf_maxmax(suf_max,height[right]);if(pre_maxsuf_max){anspre_max-height[left];left;}else{anssuf_max-height[right];--right;}}returnans;}};复杂度分析时间复杂度O(n)每个元素被访问一次。空间复杂度O(1)只使用了常数个变量。方法三单调栈思路分析单调栈解法通过维护一个递减栈来寻找凹槽并按层计算积水量。栈中存储的是柱子的下标保证从栈底到栈顶对应的高度是递减的。遍历每个柱子如果当前柱子高度小于等于栈顶高度则入栈维持递减。如果当前柱子高度大于栈顶高度说明栈顶柱子可以作为凹槽的底部。弹出栈顶作为bottom此时新的栈顶就是凹槽的左边界left当前柱子i是右边界。那么这一层的积水高度为min(height[left], height[i]) - height[bottom]宽度为i - left - 1累加结果。重复这个过程直到栈空或栈顶高度不小于当前高度。注意当高度相等时我们同样会弹出旧的栈顶并用新的下标代替这样可以避免重复计算且不影响最终结果。代码实现classSolution{public:inttrap(vectorintheight){intans0;stackintst;// 存储下标保证栈中高度递减for(inti0;iheight.size();i){inthheight[i];while(!st.empty()height[st.top()]h){intbottom_hheight[st.top()];st.pop();if(st.empty())break;// 左边没有更高的柱子无法形成凹槽intleftst.top();intdhmin(height[left],h)-bottom_h;// 这一层的高度intwidthi-left-1;ansdh*width;}st.push(i);}returnans;}};复杂度分析时间复杂度O(n)每个元素入栈一次出栈一次。空间复杂度O(n)栈在最坏情况下需要存储所有下标如高度递减的情况。三种方法对比方法时间复杂度空间复杂度核心思想前缀后缀O(n)O(n)预先计算每个位置左右的最大值直接累加双指针O(n)O(1)动态维护左右最大高度每次处理较矮一侧单调栈O(n)O(n)用递减栈寻找凹槽按层计算水量前缀后缀最容易理解但空间开销较大。双指针是空间最优解代码简洁面试中常被要求写出。单调栈思路巧妙适合作为扩展解法体现对问题结构的深入理解。总结接雨水问题是一道经典的面试题三种解法分别代表了动态规划、双指针、单调栈三种不同的思想。掌握它们不仅能解决本题还能帮助你处理其他类似问题如柱状图中最大的矩形、每日温度等。