Leetcode 42. Trapping Rain Water

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.

双指针：把题意简化到左右高已知，中间部分全部低于左右两边，就很容易求出能放多少水，因此对于这道题，可以用双指针一直记录当前左右两边的最大值。

栈：如果利用栈，我们从左到右每把一个元素放入栈内时，可以看它是否比栈顶元素的高度大，如果比栈顶大，则说明当前元素可以当做之前这个元素的一个右边栏，如果比栈顶小，则栈顶元素可以当做当前元素的一个左边栏。

动态规划：如果对于每个元素，我们能知道它左边最大的高度（包括它自身），右边最大的高度（包括它自身），那么对于这个元素的位置能放的最大水量，就等于它左右两边较小的最大高度减去自身高度。遍历完整个数组，对每个位置的最大水量求和就是总最大水量。

//双指针法
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;
    }

  //单调栈
  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;
    }

  //动态规划
  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;
    }