題目

給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖懊渡，計(jì)算按此排列的柱子骄呼，下雨之后能接多少雨水苍鲜。

ekR4ns

輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖胸囱，在這種情況下洽瞬，可以接 6 個(gè)單位的雨水（藍(lán)色部分表示雨水）嗡髓。

code

/**
 * @param height
 * @return
 * 當(dāng)前柱子如果小于等于棧頂元素操漠，說(shuō)明形不成凹槽，則將當(dāng)前柱子入棧饿这；反之若當(dāng)前柱子大于棧頂元素浊伙，說(shuō)明形成了凹槽，于是將棧中小于當(dāng)前柱子的元素pop出來(lái)长捧，將凹槽的大小累加到結(jié)果中嚣鄙。
 * 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狀態(tài)轉(zhuǎn)移方程
    // 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]; // 保存右邊最大

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

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

    // 遍歷 和trap_1方法相同，求出size串结，即 當(dāng)前柱子左右兩邊最大高度的較小者 - 當(dāng)前柱子的高度哑子。
    for (int i = 0; i < heights.length; i++) {
        size += Math.min(dp[i][0], dp[i][1]) - heights[i];
    }

    return size;
}

/**
 * 每個(gè)柱子頂部可以儲(chǔ)水的高度為：該柱子的左右兩側(cè)最大高度的較小者減去此柱子的高度舅列。
 * 因此我們只需要遍歷每個(gè)柱子，累加每個(gè)柱子可以儲(chǔ)水的高度即可卧蜓。
 *
 * @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;
    // 遍歷每個(gè)柱子
    for (int i = 1; i < n; i++) {
        int left_max = 0, right_max = 0;
        // 計(jì)算當(dāng)前柱子左側(cè)的柱子中的最大高度
        for (int j = 0; j <= i; j++) {
            left_max = Math.max(left_max, heights[j]);
        }
        // 計(jì)算當(dāng)前柱子右側(cè)的柱子中的最大高度
        for (int j = i; j < n; j++) {
            right_max = Math.max(right_max, heights[j]);
        }
        // 結(jié)果中累加當(dāng)前柱子頂部可以儲(chǔ)水的高度帐要，
        // 即 當(dāng)前柱子左右兩邊最大高度的較小者 - 當(dāng)前柱子的高度。
        size += Math.min(left_max, right_max) - heights[i];
    }
    return size;
}