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.

Example

Example 1:

Input: [0,1,0] Output: 0

Example 2:

Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6

思路：在某一个index，它所能够盛水的高度，取决于它向左边看的最大高度和向右看最大高度的min，然后减去当前值，就是能够盛水的值。

class Solution { public int trap(int[] height) { if(height == null || height.length == 0) { return 0; } int n = height.length; int[] left = new int[n]; left[0] = 0; for(int i = 1; i < n; i++) { left[i] = Math.max(left[i - 1], height[i - 1]); } int[] right = new int[n]; right[n - 1] = height[n - 1]; for(int i = n - 2; i >= 0; i--) { right[i] = Math.max(right[i + 1], height[i + 1]); } int water = 0; for(int i = 1; i < n - 1; i++) { water += Math.max(0, Math.min(left[i], right[i]) - height[i]); } return water; } }

思路2：需要找到每个元素从左右两边看，左右两边第一个最大的元素，water 就是左右两边最大的最小值 - 当前的height；这样用单调递减栈，注意stack里面存的是index，用来求宽度的；

class Solution { public int trap(int[] height) { if(height == null || height.length == 0) { return 0; } Stack<Integer> stack = new Stack<Integer>(); int water = 0; for(int i = 0; i < height.length; i++) { while(!stack.isEmpty() && height[stack.peek()] <= height[i]) { int j = stack.pop(); if(!stack.isEmpty()) { int left = stack.peek() + 1; int right = i - 1; int h = Math.min(height[stack.peek()], height[i]) - height[j]; water += (right - left + 1) * h; } } stack.push(i); } return water; } }