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.

雙指針：把題意簡(jiǎn)化到左右高已知，中間部分全部低于左右兩邊，就很容易求出能放多少水，因此對(duì)于這道題，可以用雙指針一直記錄當(dāng)前左右兩邊的最大值。

棧：如果利用棧，我們從左到右每把一個(gè)元素放入棧內(nèi)時(shí)，可以看它是否比棧頂元素的高度大，如果比棧頂大，則說(shuō)明當(dāng)前元素可以當(dāng)做之前這個(gè)元素的一個(gè)右邊欄，如果比棧頂小，則棧頂元素可以當(dāng)做當(dāng)前元素的一個(gè)左邊欄。

動(dòng)態(tài)規(guī)劃：如果對(duì)于每個(gè)元素，我們能知道它左邊最大的高度（包括它自身），右邊最大的高度（包括它自身），那么對(duì)于這個(gè)元素的位置能放的最大水量，就等于它左右兩邊較小的最大高度減去自身高度。遍歷完整個(gè)數(shù)組，對(duì)每個(gè)位置的最大水量求和就是總最大水量。

//雙指針?lè)?public int trap(int[] height) {
        if (height == null || height.length < 2) {
            return 0;
        }

        int len = height.length - 1;
        int left = 0, leftMax = 0, right = len, rightMax = 0;
        int maxWater = 0;

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

        return maxWater;
    }

  //單調(diào)棧
  public int trap(int[] height) {
        if (height == null || height.length < 2) {
            return 0;
        }

        int maxWater = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.empty() && height[stack.peek()] < height[i]) {
                int preHeight = height[stack.pop()];
                if (stack.empty()) {
                    break;
                }
                int dis = i - stack.peek() - 1;
                int hDiff = Math.min(height[i], height[stack.peek()]) - preHeight;
                maxWater += dis * hDiff;
            }
            stack.push(i);
        }

        return maxWater;
    }

  //動(dòng)態(tài)規(guī)劃
  public int trapDp(int[] height) {
        if (height == null || height.length < 2) {
            return 0;
        }

        int maxWater = 0;
        int size = height.length;

        int[] leftMax = new int[size];
        leftMax[0] = height[0];
        for (int i = 1; i < size; i++) {
            leftMax[i] = Math.max(leftMax[i-1], height[i]);
        }

        int[] rightMax = new int[size];
        rightMax[size-1] = height[size-1];
        for (int i = size - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i+1], height[i]);
        }

        for (int i = 0; i < size; i++) {
            maxWater += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return maxWater;
    }