42. 接雨水

题目描述

输入长度为 n 的非负整数数组 height。把它看成一排宽度都为 1 的柱子，第 i 根柱子高 height[i]，相邻柱子紧挨在一起。

下雨后，柱子之间的凹槽会积水。某一列上方的水面高度，取决于它左边最高的柱子和右边最高的柱子中较矮的那个。

返回所有列加起来一共能存住多少单位的水。

示例 1

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

解释：这组柱子之间的几处凹槽合计能存 6 个单位的水。

示例 2

输入：height = [4,2,0,3,2,5]
输出：9

解释：下标 1 到 4 处分别能存 2、4、1、2 个单位，共 9。

数据范围

n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

解题思路

左右指针维护已处理侧的最高墙。若 height[l] <= height[r]，先更新 left_max，再累加 left_max-height[l] 并右移 l；否则更新 right_max，累加 right_max-height[r] 并左移 r。

为什么正确

处理较矮一侧时，该侧的最高边界已经确定，当前位置水量可安全加入答案。

复杂度分析

时间 O(n)，空间 O(1)。

易错点

只看相邻柱高会漏掉由远处边界形成的水槽。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def trap(self, height):
        l,r=0,len(height)-1; left_max=right_max=0; ans=0
        while l < r:
            if height[l] <= height[r]:
                left_max=max(left_max,height[l]); ans += left_max-height[l]; l += 1
            else:
                right_max=max(right_max,height[r]); ans += right_max-height[r]; r -= 1
        return ans

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1, leftMax = 0, rightMax = 0, ans = 0;
        while (l < r) {
            if (height[l] <= height[r]) {
                leftMax = Math.max(leftMax, height[l]); ans += leftMax - height[l]; l++;
            } else {
                rightMax = Math.max(rightMax, height[r]); ans += rightMax - height[r]; r--;
            }
        }
        return ans;
    }
}

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

func trap(height []int) int {
	l, r, leftMax, rightMax, ans := 0, len(height)-1, 0, 0, 0
	for l < r {
		if height[l] <= height[r] {
			leftMax = max(leftMax, height[l]); ans += leftMax - height[l]; l++
		} else {
			rightMax = max(rightMax, height[r]); ans += rightMax - height[r]; r--
		}
	}
	return ans
}

var trap = function(height) {
    let l = 0, r = height.length - 1, leftMax = 0, rightMax = 0, ans = 0;
    while (l < r) {
        if (height[l] <= height[r]) {
            leftMax = Math.max(leftMax, height[l]); ans += leftMax - height[l]; l++;
        } else {
            rightMax = Math.max(rightMax, height[r]); ans += rightMax - height[r]; r--;
        }
    }
    return ans;
};

function trap(height: number[]): number {
    let l = 0, r = height.length - 1, leftMax = 0, rightMax = 0, ans = 0;
    while (l < r) {
        if (height[l] <= height[r]) {
            leftMax = Math.max(leftMax, height[l]); ans += leftMax - height[l]; l++;
        } else {
            rightMax = Math.max(rightMax, height[r]); ans += rightMax - height[r]; r--;
        }
    }
    return ans;
};

载入编辑器，自己跑一遍 →

其他解法

前后缀最大值和双指针都按列求水量，后者把 O(n) 数组压成 O(1) 变量；单调栈按层求水量，同样 O(n) 时间但需要栈空间。

解法 2：前后缀最大值时间 O(n)，空间 O(n)

位置 i 的水面高度等于它左侧最高柱和右侧最高柱中的较小者。从左到右算出 leftMax[i]，从右到左算出 rightMax[i]。答案是所有 min(leftMax[i], rightMax[i]) - height[i] 之和。

思路最直接，是理解双指针解法的前置步骤。需要两个长度为 n 的数组；双指针正是把这两个数组压缩成两个变量。

class Solution:
    def trap(self, height):
        n = len(height)
        if n == 0:
            return 0
        left_max = [0] * n
        right_max = [0] * n
        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])
        right_max[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])
        ans = 0
        for i in range(n):
            ans += min(left_max[i], right_max[i]) - height[i]
        return ans

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;
        int[] leftMax = new int[n], rightMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        int ans = 0;
        for (int i = 0; i < n; i++) ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        return ans;
    }
}

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) return 0;
        vector<int> leftMax(n), rightMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) leftMax[i] = max(leftMax[i - 1], height[i]);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) rightMax[i] = max(rightMax[i + 1], height[i]);
        int ans = 0;
        for (int i = 0; i < n; i++) ans += min(leftMax[i], rightMax[i]) - height[i];
        return ans;
    }
};

func trap(height []int) int {
	n := len(height)
	if n == 0 {
		return 0
	}
	leftMax := make([]int, n)
	rightMax := make([]int, n)
	leftMax[0] = height[0]
	for i := 1; i < n; i++ {
		leftMax[i] = max(leftMax[i-1], height[i])
	}
	rightMax[n-1] = height[n-1]
	for i := n - 2; i >= 0; i-- {
		rightMax[i] = max(rightMax[i+1], height[i])
	}
	ans := 0
	for i := 0; i < n; i++ {
		ans += min(leftMax[i], rightMax[i]) - height[i]
	}
	return ans
}

var trap = function(height) {
    const n = height.length;
    if (n === 0) return 0;
    const leftMax = new Array(n), rightMax = new Array(n);
    leftMax[0] = height[0];
    for (let i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    rightMax[n - 1] = height[n - 1];
    for (let i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    let ans = 0;
    for (let i = 0; i < n; i++) ans += Math.min(leftMax[i], rightMax[i]) - height[i];
    return ans;
};

function trap(height: number[]): number {
    const n = height.length;
    if (n === 0) return 0;
    const leftMax: number[] = new Array(n), rightMax: number[] = new Array(n);
    leftMax[0] = height[0];
    for (let i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    rightMax[n - 1] = height[n - 1];
    for (let i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    let ans = 0;
    for (let i = 0; i < n; i++) ans += Math.min(leftMax[i], rightMax[i]) - height[i];
    return ans;
}

解法 3：单调栈时间 O(n)，空间 O(n)

维护一个下标栈，栈内高度单调不增。遇到比栈顶更高的柱子时，弹出栈顶作为坑底，新栈顶是左墙，当前柱子是右墙。这一层水的体积为 (i - left - 1) × (min(左墙, 右墙) - 坑底)，累加到答案。

按层横向计算水量，和前两种按列纵向计算的思路互补。需要 O(n) 栈空间，代码细节比双指针多，但同一套路可用于柱状图最大矩形等题。

class Solution:
    def trap(self, height):
        ans = 0
        stack = []
        for i, h in enumerate(height):
            while stack and h > height[stack[-1]]:
                bottom = stack.pop()
                if not stack:
                    break
                left = stack[-1]
                width = i - left - 1
                bounded = min(height[left], h) - height[bottom]
                ans += width * bounded
            stack.append(i)
        return ans

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < height.length; i++) {
            while (!st.isEmpty() && height[i] > height[st.peek()]) {
                int bottom = st.pop();
                if (st.isEmpty()) break;
                int left = st.peek();
                int width = i - left - 1;
                int bounded = Math.min(height[left], height[i]) - height[bottom];
                ans += width * bounded;
            }
            st.push(i);
        }
        return ans;
    }
}

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        vector<int> st;
        for (int i = 0; i < (int)height.size(); i++) {
            while (!st.empty() && height[i] > height[st.back()]) {
                int bottom = st.back();
                st.pop_back();
                if (st.empty()) break;
                int left = st.back();
                int width = i - left - 1;
                int bounded = min(height[left], height[i]) - height[bottom];
                ans += width * bounded;
            }
            st.push_back(i);
        }
        return ans;
    }
};

func trap(height []int) int {
	ans := 0
	st := []int{}
	for i, h := range height {
		for len(st) > 0 && h > height[st[len(st)-1]] {
			bottom := st[len(st)-1]
			st = st[:len(st)-1]
			if len(st) == 0 {
				break
			}
			left := st[len(st)-1]
			width := i - left - 1
			bounded := min(height[left], h) - height[bottom]
			ans += width * bounded
		}
		st = append(st, i)
	}
	return ans
}

var trap = function(height) {
    let ans = 0;
    const st = [];
    for (let i = 0; i < height.length; i++) {
        while (st.length && height[i] > height[st[st.length - 1]]) {
            const bottom = st.pop();
            if (!st.length) break;
            const left = st[st.length - 1];
            const width = i - left - 1;
            const bounded = Math.min(height[left], height[i]) - height[bottom];
            ans += width * bounded;
        }
        st.push(i);
    }
    return ans;
};

function trap(height: number[]): number {
    let ans = 0;
    const st: number[] = [];
    for (let i = 0; i < height.length; i++) {
        while (st.length && height[i] > height[st[st.length - 1]]) {
            const bottom = st.pop()!;
            if (!st.length) break;
            const left = st[st.length - 1];
            const width = i - left - 1;
            const bounded = Math.min(height[left], height[i]) - height[bottom];
            ans += width * bounded;
        }
        st.push(i);
    }
    return ans;
}

双指针专题的其他题目

查看双指针全部题目 →