0042. Trapping Rain Water - kumaeki/LeetCode GitHub Wiki

0042. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]

Output: 9

Constraints:

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

解法1

储藏的水由左右两侧中比较矮的那边决定.

class Solution {
    public int trap(int[] height) {
        if(height == null || height.length <3)
            return 0;
        
        int res = 0, len = height.length;

        // 从左到右, 到当前位置为止最高的高度
        int[] left = new int[len];
        left[0] = height[0];
        for (int i = 1; i < len; i++)
            left[i] = Math.max(left[i - 1], height[i]);

        // 从右到左, 到当前位置为止最高的高度
        int[] right = new int[len];
        right[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--)
            right[i] = Math.max(right[i + 1], height[i]);

        // 储存的水由左右侧较矮的那边决定
        for (int i = 0; i < len; i++)
            res += (Math.min(left[i], right[i]) - height[i]);

        return res;
    }
}

解法2

解法1的优化, 我们定义左右两个游标, 从两侧往中间走.

class Solution {
    public int trap(int[] height) {
        int res = 0, left = 0, right = height.length - 1;
        int maxL = 0, maxR = 0;
        while (left < right) {
            int hl = height[left], hr = height[right];
            if (hl <= hr) {
                if (hl >= maxL)
                    maxL = hl;
                else
                    res += (maxL - hl);
                left++;
            } else {
                if (hr >= maxR)
                    maxR = hr;
                else
                    res += (maxR - hr);
                right--;
            }
        }

        return res;
    }
}

解法3

class Solution {
    public int trap(int[] height) {

        int res = 0, len = height.length;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int low = stack.pop();
                if (!stack.isEmpty()) {
                    int w = i - stack.peek() - 1;
                    res += (Math.min(height[i], height[stack.peek()]) - height[low]) * w;
                }
            }
            stack.push(i);
        }

        return res;
    }
}
⚠️ **GitHub.com Fallback** ⚠️