42. Trapping Rain Water

Mono Stack

```java
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        Stack<Integer> stack = new Stack<>(); // index
        int result = 0;
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int base = height[stack.pop()];
                if (!stack.isEmpty()) {
                    int leftBoundIndex = stack.peek();
                    int leftHeight = height[leftBoundIndex];
                    result += (Math.min(height[i], leftHeight) - base)*(i - leftBoundIndex - 1);
                }
            }
            stack.push(i);
        }
        return result;
    }
}

/***

min(hi, left side) - base idea

2,1,0,1,3
    x x x

        3
2.x x x 3  
2 1 x 1 3
2 1 0.1 3 
      curH
    base = pop
  left = peek

  (min(leftH, curH) - base)* (index diff)


        3
2.x x x 3
2 1 x 1 3

3.  cur H
   1 -> base
1. -> peek
2  -> peek

min(3, 1) - base (1) = 0
min(3, 2) - base (1) = 1

 */
```

Two pointers

-----

if (h[left] < h[right] )

最左開始找最大的 left, left++

else

最右開使找最大的 right, right--

目的是為了找到 descending 的時候, 也就是有積水, 根本不用管中間的值

看最左 最右就得得知

descending!

其實左 跟 右做的事雷同, 所以只是變數改成 right, right--

if (height[left] < height[right]) { // 因為左邊比較小, 先做 left
    ....
    left++;

class Solution {
    public int trap(int[] height) {
        // two pointers
        // h[left] > h[right]
        // leftmax > h[left] => res += leftmax - res
        int left = 0;
        int right = height.length - 1;
        int leftMax = 0;
        int rightMax = 0;
        int res = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                leftMax = Math.max(leftMax, height[left]);
                res += leftMax - height[left];
                left++;
            } else {
                rightMax = Math.max(rightMax, height[right]);
                res += rightMax - height[right];
                right--;
            }
        }
        return res;
    }
}

如果是用 left right 指針

要算雨水面積, 對 left 的左邊, 我們只關心最大的 maxleft 是多少 （如果我們都決定是走左邊的話, 因為我們都想要取比較低的那一邊, 所以如果 max_left 比較小, 那走左邊的比較和計算

反之走右邊

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int left = 0;
        int right = n-1;
        int maxLeft = 0;
        int maxRight = 0;
            
        int result = 0;
        while (left < right) {
            maxLeft = Math.max(maxLeft, height[left]);
            maxRight = Math.max(maxRight, height[right]);
            
            if (maxLeft < maxRight) {
                result += maxLeft - height[left];
                left++;
            } else {
                result += maxRight - height[right];
                right--;
            }
        }
        return result;
    }
}

use this

不過我認為這個解法比較好懂

如何能構成有雨水呢？ 找左邊最高的 和右邊最高的, 比較低的 可以有雨水（要扣掉自己本身的高度

T: O(n)

S: O(n)

class Solution {
    public int trap(int[] height) {
        int 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]);
        }
        int result = 0;
        for (int i = 0; i < n; i++) {
            result += Math.min(maxLeft[i] , maxRight[i]) - height[i];
        }
        return result;
    }
}