Trapping Rain Water (H)

題目

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

The above elevation map 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. Thanks Marcos for contributing this image!

Example:

Input: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6

題意

計算由給定陣列構成的高度圖能夠存盤的最大水量(圖中藍色區域)，

思路

暴力法：對于每一個下標位置，當前位置高度為cur，找到它左側的最大高度leftMax，及右側的最大高度rightMax，如果兩者都大于cur，說明在當前位置可以存水，可存水量為min(leftMax, rightMax) - cur，復雜度為\(O(N^2)\)，(一開始想到的暴力法是奇葩的從下往上掃描找空格hhh)

動態規劃優化的暴力法：暴力法效率較低的原因在于每一次都要重新計算左右兩側的最大高度，通過動態規劃提前將每個位置左右兩側的最大高度記錄下來可以大大提高效率，復雜度為\(O(N)\)，
記dp[i]為以i為端點的左/右區間中的最大高度，那么有 \(dp[i]=max(dp[i-1],\ height[i])\)，

官方解答還提供了壓堆疊法和Two pointers解法，

壓堆疊法：從左到右遍歷陣列，若堆疊慷訓當前下標cur對應高度小于堆疊頂下標top對應高度，則將cur壓入堆疊，這保證了堆疊中每一個下標的高度是遞減的；若 height[cur] > height[top]，同時top的高度又小于堆疊中前一個下標對應的高度，說明在下標top處可以存水(左右兩邊高度大于height[top])，將top出堆疊并計算存盤的水量，重復上述程序直到cur對應高度不大于此時堆疊頂下標高度，將cur壓入堆疊，

Two Pointers：左右兩邊各設一個指標left和right向中間移動，每次判斷，如果 height[left] < height[right]，且 height[left] < leftMax，說明left位置被leftMax和height[right]包圍，可以存水，若 height[left] > leftMax，則更新leftMax；如果 height[right] <= height[left]，且 height[right] < rightMax，說明right位置被rightMax和height[left]包圍，可以存水，若 height[right] < rightMax，則更新rightMax，

代碼實作

Java

動態規劃優化

class Solution {
    public int trap(int[] height) {
        if (height.length == 0) {
            return 0;
        }
        
        int sum = 0;
        int[] leftMaxHeight = new int[height.length];
        int[] rightMaxHeight = new int[height.length];
        
        // 動態規劃記錄左右最大高度資訊
        leftMaxHeight[0] = height[0];
        rightMaxHeight[height.length - 1] = height[height.length - 1];
        for (int i = 1; i < height.length - 1; i++) {
            int j = height.length - i - 1;
            leftMaxHeight[i] = Math.max(leftMaxHeight[i - 1], height[i]);
            rightMaxHeight[j] = Math.max(rightMaxHeight[j + 1], height[j]);
        }
        
        for (int i = 0; i < height.length; i++) {
            int leftMax = leftMaxHeight[i];
            int rightMax = rightMaxHeight[i];
            if (leftMax > height[i] && rightMax > height[i]) {
                sum += Math.min(leftMax, rightMax) - height[i];
            }
        }

        return sum;
    }
}

壓堆疊法

class Solution {
    public int trap(int[] height) {
        int sum = 0, cur = 0;
        Deque<Integer> stack = new ArrayDeque<>();

        while (cur < height.length) {
            while (!stack.isEmpty() && height[cur] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int dx = cur - stack.peek() - 1;
                int dy = Math.min(height[cur], height[stack.peek()]) - height[top];
                sum += dx * dy;
            }
            stack.push(cur++);
        }
        
        return sum;
    }
}

Two Pointers

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        int left = 0, right = height.length - 1;
        int leftMax = -1, rightMax = -1;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] > leftMax) {
                    leftMax = height[left];
                } else {
                    sum += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] > rightMax) {
                    rightMax = height[right];
                } else {
                    sum += rightMax - height[right];
                }
                right--;
            }
        }

        return sum;
    }
}

JavaScript

動態規劃優化

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let len = height.length
  let left = new Array(len).fill(0)
  let right = new Array(len).fill(0)

  for (let i = 1; i < len; i++) {
    left[i] = Math.max(left[i - 1], height[i - 1])
    right[len - 1 - i] = Math.max(right[len - i], height[len - i])
  }

  let sum = 0
  for (let i = 1; i < len - 1; i++) {
    if (left[i] > height[i] && right[i] > height[i]) {
      sum += Math.min(left[i], right[i]) - height[i]
    }
  }

  return sum
}

壓堆疊法

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let sum = 0
  let stack = []

  for (let i = 0; i < height.length; i++) {
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      let j = stack.pop()
      if (stack.length === 0) {
        break
      }
      let k = stack[stack.length - 1]
      let dx = i - k - 1
      let dy = Math.min(height[i], height[k]) - height[j]
      sum += dx * dy
    }
    stack.push(i)
  }

  return sum
}

Two Pointers

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let sum = 0
  let left = 0, right = height.length - 1
  let leftMax = -1, rightMax = -1

  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] > leftMax) {
        leftMax = height[left++]
      } else {
        sum += leftMax - height[left++]
      }
    } else {
      if (height[right] > rightMax) {
        rightMax = height[right--]
      } else {
        sum += rightMax - height[right--]
      }
    }
  }

  return sum
}

標籤：其他

上一篇：14.非平衡樹的雙旋（左右雙旋和右左雙旋和右右雙旋和左左雙旋）代碼實作（JavaScript版）

下一篇：0043. Multiply Strings (M)