lc42接雨水

1.原题

42. 接雨水 - 力扣（LeetCode）

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

2.题目解析

这一题是经常被考到的一道算法题，其中最简单最好用的方法就是双指针，今天我们就以双指针的角度来解决这一题！

2.1动态规划写法

我们先从动态规划的角度引入双指针的视角！

在计算数组height中下标i处接雨水量时，存在这样一个规律：下雨后水在该位置能达到的最大高度，等同于i两侧高度中的最小值，而i处实际能承接的雨水量，就是这个最大高度减去height[i]的值。

如果采用最基础的解决方式，针对数组height里的每一个元素，都需要分别朝左、右方向进行扫描，记录下左右两边的最大高度，进而算出每个下标位置能承接的雨水量。若数组height长度为n，由于对每个下标位置进行左右扫描都要耗费O(n)的时间，最终整体的时间复杂度会达到O(n²) 。

这种基础做法之所以耗时较长，根源在于对每个下标位置都要重复执行左右扫描操作。要是能提前获取每个位置两侧的最大高度，就能将计算能接雨水总量的时间复杂度降至O(n)。借助动态规划的思路，恰好可以在O(n)时间内预先处理并得到每个位置两侧的最大高度。

具体操作时，我们构建两个长度同为n的数组leftMax和rightMax。其中，leftMax[i]代表从数组起始位置到下标i这一范围内，height的最大高度；rightMax[i]则表示从下标i到数组末尾，height的最大高度。

不难发现，leftMax数组的第一个元素leftMax[0]，其值就等于height[0]；rightMax数组的最后一个元素rightMax[n - 1]，对应的值为height[n - 1]。至于两个数组的其他元素，计算规则如下：

• 当1 ≤ i ≤ n - 1时，leftMax[i]取leftMax[i - 1]和height[i]中的较大值；

• 当0 ≤ i ≤ n - 2时，rightMax[i]是rightMax[i + 1]和height[i]中的较大值。

基于此，我们可以通过正向遍历数组height，逐个算出leftMax数组的元素值；再反向遍历数组height，得到rightMax数组的每个元素值。

在获取leftMax和rightMax数组的全部元素值后，对于0 ≤ i < n范围内的每个i，其下标位置能承接的雨水量就等于min(leftMax[i], rightMax[i]) - height[i]。最后，遍历所有下标位置，将每个位置的接雨水量累加起来，便能得到最终能承接的雨水总量。

2.2引入双指针写法

在动态规划解法中，需借助leftMax和rightMax两个数组记录各位置左右两侧的最大高度，这导致空间复杂度为O(n)。那么，能否进一步优化空间复杂度至O(1)呢？答案是肯定的。通过观察发现，每个位置的储水量仅由其左右两侧最大高度的较小值决定，而双指针技术可巧妙利用这一特性，用两个变量替代数组存储中间状态。

核心思路：双指针与变量维护

我们引入两个指针left和right，分别指向数组首尾两端，同时用两个变量left_max和right_max动态记录当前左右指针处的历史最大高度。具体逻辑如下：

1. 初始化：left = 0，right = n-1，left_max = 0，right_max = 0。

1. 指针移动规则：当height[left] < height[right]时，说明左侧当前高度较低，其储水量由左侧历史最大高度决定。此时计算left位置的储水量，并右移left指针。当height[left] ≥ height[right]时，说明右侧当前高度较低，其储水量由右侧历史最大高度决定。此时计算right位置的储水量，并左移right指针。
2. 动态更新最大高度：每次处理指针位置前，先更新对应方向的历史最大高度（left_max或right_max）。

具体实现步骤

假设数组长度为n，初始时双指针未相遇（left < right），循环执行以下操作：

1. 更新历史最大高度：
2. left_max = max(left_max, height[left])
3. right_max = max(right_max, height[right])
4. 比较当前指针处高度：
5. 若height[left] < height[right]：
6. 此时左侧最大高度left_max必然小于等于右侧最大高度right_max（因height[left]是较小值），故left位置的储水量为 left_max - height[left]。
7. 将该值累加到总储水量，然后left++。
8. 若height[left] ≥ height[right]：
9. 此时右侧最大高度right_max必然小于等于左侧最大高度left_max，故right位置的储水量为 right_max - height[right]。
10. 将该值累加到总储水量，然后right--。
11. 循环终止条件：当left == right时，遍历结束，返回总储水量。

关键逻辑推导

• 为什么可以用单变量替代数组？当height[left] < height[right]时，left位置的右侧最大高度至少为height[right]（后续right指针左移可能遇到更高高度），但储水量由左右两侧的较小值决定。由于height[left]是当前较小值，其左侧最大高度left_max已确定为左侧全局最大值，因此无需记录右侧所有位置的最大值，只需保证left_max是左侧历史最大值即可。同理适用于右侧情况。

复杂度分析

• 时间复杂度：O(n)，每个元素仅被左右指针各访问一次。

• 空间复杂度：O(1)，仅使用常数级额外空间（指针和变量）。

总结

通过双指针技术，我们避免了存储两个完整数组，将空间复杂度从O(n)优化至O(1)，同时保持线性时间复杂度。该解法的核心在于利用左右指针的相对高度关系，动态确定当前位置的储水量由哪一侧的最大高度主导，从而实现空间效率的显著提升。

3.双指针写法代码

class Solution {
public:int trap(vector<int>& v) {int n=v.size();int l=0;int r=n-1;int ans=0;int lmax=0,rmax=0;while(l<=r){lmax=max(lmax,v[l]);rmax=max(rmax,v[r]);if(v[r]>=v[l]){ans+=lmax-v[l];l++;}else {ans+=rmax-v[r];r--;}}return ans;}
};

本题解为参考力扣题解后的总结！