42. 接雨水

暴力法

class Solution {
    public int trap(int[] height) {
        int res = 0, n = height.length;
        // 从height[1..n-1]，因为两端无积水
        for (int i = 1; i < n - 1; i++) {
            int maxLeft = 0, maxRight = 0;
            // 找到左边的最大值
            for (int j = i; j >= 0; j--) {
                maxLeft = Math.max(height[j], maxLeft);
            }
            // 找到右边的最大值
            for (int j = i; j < n; j++) {
                maxRight = Math.max(height[j], maxRight);
            }
            // 加上两边最大高度的较小值，减去当前高度
            res += Math.min(maxLeft, maxRight) - height[i];
        }
        return res;
    }
}

• 时间复杂度 O(n²)
• 空间复杂度 O(1)

动态规划

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

        int res = 0, n = height.length;
        int[] maxLeft = new int[n];
        int[] maxRight = new int[n];

        // 往左的最大值
        maxLeft[0] = height[0];
        for (int i = 1; i < n; i++) {
            maxLeft[i] = Math.max(height[i], maxLeft[i - 1]);
        }

        // 往右的最大值
        maxRight[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            maxRight[i] = Math.max(height[i], maxRight[i + 1]);
        }

        // 从height[1..n-1]，因为两端无积水
        for (int i = 1; i < n - 1; i++) {
            // 加上两边最大高度的较小值，减去当前高度
            res += Math.min(maxLeft[i], maxRight[i]) - height[i];
        }
        return res;
    }
}

• 时间复杂度 O(n)
• 空间复杂度 O(n)

单调栈

class Solution {
    public int trap(int[] height) {
        int res = 0, i = 0;
        Stack<Integer> stack = new Stack<>();
        while (i < height.length) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int distance = i - stack.peek() - 1;
                int bounded_height = Math.min(height[i], height[stack.peek()]) - height[top];
                res += distance * bounded_height;
            }
            stack.push(i++);
        }
        return res;
    }
}

• 时间复杂度 O(n)
• 空间复杂度 O(n)

双指针

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1;
        int res = 0;
        int maxLeft = 0, maxRight = 0;
        while (l < r) {
            // 如果当前 左指针的高度 小于 右指针的高度，则说明 两边最大高度的较小值肯定在左边,所以就只用看maxLeft
            // 否则说明 两边最大高度的较小值肯定在右边边,所以就只用看maxRight
            if (height[l] < height[r]) {
                if (height[l] >= maxLeft) {
                    maxLeft = height[l];
                } else {
                    res += maxLeft - height[l];
                }
                l++;
            } else {
                if (height[r] >= maxRight) {
                    maxRight = height[r];
                } else {
                    res += maxRight - height[r];
                }
                r--;
            }
        }
        return res;
    }
}

• 时间复杂度 O(n)
• 空间复杂度 O(1)