接雨水

题意

给定 n 个非负整数表示柱状图高度，计算能接多少雨水。

思路

每个位置能接的水量 = min(左边最高柱, 右边最高柱) - 自身高度。

暴力 O(n²) 每位置独立查左右最大值。优化方法有三种：

前后缀最大值：预计算 left_max 和 right_max，O(n) 空间。
单调栈：按凹槽结算，遇到更高的柱子就弹出结算。
双指针：左右指针各维护一个当前最高柱，较矮侧的水量可立即确定，并移动该侧指针。无需额外数组。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35/**
 * Author by Rainboy
 */
// main.cpp：双指针维护左右最高柱，较矮侧水量可立即确定，O(n) O(1)。
#include <bits/stdc++.h>
using namespace std;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> h(n);
    for (int &x : h)
        cin >> x;
    cout << Solution().trap(h) << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#!/usr/bin/env python3
from typing import List


class Solution:
    def trap(self, height: List[int]) -> int:
        l, r, lmax, rmax, ans = 0, len(height) - 1, 0, 0, 0
        while l < r:
            if height[l] < height[r]:
                if height[l] >= lmax:
                    lmax = height[l]
                else:
                    ans += lmax - height[l]
                l += 1
            else:
                if height[r] >= rmax:
                    rmax = height[r]
                else:
                    ans += rmax - height[r]
                r -= 1
        return ans


def main() -> None:
    n = int(input())
    height = list(map(int, input().split()))
    print(Solution().trap(height))


if __name__ == "__main__":
    main()

复杂度

时间复杂度：O(n)，双指针各遍历一次。
空间复杂度：O(1)，只使用几个变量。

总结

双指针解法的核心不变量是：lmax 是 [0..l] 的最大值，rmax 是 [r..n-1] 的最大值。height[l] < height[r] 时，lmax < rmax 不一定成立，但左侧水量由 lmax 决定已足够，因为 rmax 至少为 height[r]，而 height[r] > height[l] 保证了右侧有足够高的墙。

目录

题意

思路

代码

复杂度

总结