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.

雙指針：把題意簡化到左右高已知秩伞，中間部分全部低于左右兩邊刑巧，就很容易求出能放多少水，因此對于這道題，可以用雙指針一直記錄當前左右兩邊的最大值。

棧：如果利用棧福青，我們從左到右每把一個元素放入棧內(nèi)時犹菱，可以看它是否比棧頂元素的高度大，如果比棧頂大肪跋，則說明當前元素可以當做之前這個元素的一個右邊欄，如果比棧頂小土砂，則棧頂元素可以當做當前元素的一個左邊欄州既。

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

//雙指針法
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;
    }

  //動態(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;
    }