Java：接雨水

//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 
//
// 
              //
// 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Mar
//cos 贡献此图。 
//
// 示例: 
//
// 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
//输出: 6 
// Related Topics 栈 数组 双指针

package leetcode.editor.cn;

import java.util.Stack;

//Java：接雨水
public class P42TrappingRainWater {
    public static void main(String[] args) {
        Solution solution = new P42TrappingRainWater().new Solution();
        // TO TEST
        System.out.println(solution.trap(new int[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int trap(int[] height) {
            // 一开始的想法
            // 小于三个方块储存不了水
            int size = height.length;
            if (size < 3) {
                return 0;
            }
            int[] leftMaxArray = new int[size];
            Stack<Integer> rightMaxStack = new Stack<>();
            int leftMax = 0;
            int rightMax = 0;
            for (int i = 0; i < size; i++) {
                leftMaxArray[i] = leftMax;
                int curLeft = height[i];
                if (curLeft > leftMax) {
                    leftMax = curLeft;
                }
                rightMaxStack.push(rightMax);
                int curRight = height[size - i - 1];
                if (curRight > rightMax) {
                    rightMax = curRight;
                }
            }
            // 计算储水量
            int sum = 0;
            for (int i = 0; i < size; i++) {
                rightMax = rightMaxStack.pop();
                leftMax = leftMaxArray[i];
                int min = leftMax > rightMax ? rightMax : leftMax;
                int curValue = height[i];
                if (min > curValue) {
                    sum += min - curValue;
                }
            }
            return sum;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}