（6）LeetCode.42 接雨水

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(vector<int>&height){intn=height.size();vector<int>pre_max(n);pre_max[0]=height[0];for(inti=1;i<n;++i)pre_max[i]=max(pre_max[i-1],height[i]);vector<int>suf_max(n);suf_max[n-1]=height[n-1];for(inti=n-2;i>=0;--i)suf_max[i]=max(suf_max[i+1],height[i]);intans=0;for(inti=0;i<n;++i)ans+=min(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_max>pre_max，所以min(左侧最大, 右侧最大) = pre_max，该位置接水量确定。移动指针后，新的pre_max或suf_max会更新，继续处理下一个位置。

代码实现

classSolution{public:inttrap(vector<int>&height){intans=0,pre_max=0,suf_max=0;intleft=0,right=height.size()-1;while(left<right){pre_max=max(pre_max,height[left]);suf_max=max(suf_max,height[right]);if(pre_max<suf_max){ans+=pre_max-height[left];++left;}else{ans+=suf_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(vector<int>&height){intans=0;stack<int>st;// 存储下标，保证栈中高度递减for(inti=0;i<height.size();++i){inth=height[i];while(!st.empty()&&height[st.top()]<=h){intbottom_h=height[st.top()];st.pop();if(st.empty())break;// 左边没有更高的柱子，无法形成凹槽intleft=st.top();intdh=min(height[left],h)-bottom_h;// 这一层的高度intwidth=i-left-1;ans+=dh*width;}st.push(i);}returnans;}};

复杂度分析

• 时间复杂度：O(n)，每个元素入栈一次，出栈一次。
• 空间复杂度：O(n)，栈在最坏情况下需要存储所有下标（如高度递减的情况）。

三种方法对比

• 前缀后缀最容易理解，但空间开销较大。
• 双指针是空间最优解，代码简洁，面试中常被要求写出。
• 单调栈思路巧妙，适合作为扩展解法，体现对问题结构的深入理解。

总结

接雨水问题是一道经典的面试题，三种解法分别代表了动态规划、双指针、单调栈三种不同的思想。掌握它们不仅能解决本题，还能帮助你处理其他类似问题（如柱状图中最大的矩形、每日温度等）。