leetcode.42 接雨水

题目

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

ekR4ns

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

code

/**
 * @param height
 * @return
 * 当前柱子如果小于等于栈顶元素，说明形不成凹槽，则将当前柱子入栈；反之若当前柱子大于栈顶元素，说明形成了凹槽，于是将栈中小于当前柱子的元素pop出来，将凹槽的大小累加到结果中。
 * https://mp.weixin.qq.com/s/f9ebzbwymR8jQeUDxjeCDA
 */
private static int trap_3(int[] height) {
    Stack<Integer> stack = new Stack<>();
    int size = 0;
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
            Integer bottom_idx = stack.pop();

            while (!stack.isEmpty() && height[bottom_idx] == height[stack.peek()]) {
                stack.pop();
            }

            if (!stack.isEmpty()) {
                size += (Math.min(height[i], height[stack.peek()]) - height[i]) * (i - stack.peek() - 1);
            }
        }
        stack.push(i);
    }
    return size;
}

private static int trap_2(int[] heights) {
    // dp状态转移方程
    // dp[i][0] = max(dp[i - 1][0],cur)
    // dp[i][1] = max(dp[i + 1][1],cur)
    if (heights == null || heights.length == 0) {
        return 0;
    }
    int size = 0;
    int n = heights.length;
    int[][] dp = new int[n][2];

    dp[0][0] = heights[0]; // 保存左边最大
    dp[n - 1][1] = heights[n - 1]; // 保存右边最大

    // 计算左边最大
    for (int i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], heights[i]);
    }

    // 计算右边最大
    for (int i = n - 2; i >= 0; i--) {
        dp[i][1] = Math.max(dp[i + 1][1], heights[i]);
    }

    // 遍历 和trap_1方法相同，求出size，即 当前柱子左右两边最大高度的较小者 - 当前柱子的高度。
    for (int i = 0; i < heights.length; i++) {
        size += Math.min(dp[i][0], dp[i][1]) - heights[i];
    }

    return size;
}

/**
 * 每个柱子顶部可以储水的高度为：该柱子的左右两侧最大高度的较小者减去此柱子的高度。
 * 因此我们只需要遍历每个柱子，累加每个柱子可以储水的高度即可。
 *
 * @param heights
 * @return
 */
private static int trap_1(int[] heights) {
    if (heights == null || heights.length == 0) {
        return 0;
    }

    int n = heights.length;
    int size = 0;
    // 遍历每个柱子
    for (int i = 1; i < n; i++) {
        int left_max = 0, right_max = 0;
        // 计算当前柱子左侧的柱子中的最大高度
        for (int j = 0; j <= i; j++) {
            left_max = Math.max(left_max, heights[j]);
        }
        // 计算当前柱子右侧的柱子中的最大高度
        for (int j = i; j < n; j++) {
            right_max = Math.max(right_max, heights[j]);
        }
        // 结果中累加当前柱子顶部可以储水的高度，
        // 即 当前柱子左右两边最大高度的较小者 - 当前柱子的高度。
        size += Math.min(left_max, right_max) - heights[i];
    }
    return size;
}