42. Trapping Rain Water - pangeneral/leetcode-notebook GitHub Wiki

Apparently, we need two nonadjacent bars to save water, and there must be at least one valley bar between them. For bar[i], if we can find bar[j] and bar[k] where bar[j] > bar[i], bar[k] > bar[i] and j < i < k, then bar[i] is a valley bar. For example, if we have a bar sequence [5, 3, 2, 4] then 2 and 3 are both valley bars.

Therefore, the key point of this problem is finding all the valley bars. Here, we use a monotone stack to help us find these valley bars.

At first, we ignore the front bars whose length is zero. While bar[i] (current bar) is larger than the top element in the stack, then the top element is popped out of the stack (it is a candidate valley bar) and then we judge whether the stack is empty. If the stack is empty, then the popped bar is not a valley bar since we only have right holder (current bar). If the stack is not empty, then the top element, the candidate valley bar and current bar form a valid water holder. The height of the holder is (Math.min(height[i], height[stack.peek()]) - current) and the width is i - stack.peek() - 1, the holder can hold width * height water.

public int trap(int[] height) {
    Stack<Integer> stack = new Stack<Integer>();
    int begin = 0, result = 0;
    while( begin < height.length && height[begin] == 0 ) // ignore the first n bars whose length is zero
	begin++;
    for(int i = begin; i < height.length; i++) {
	while( !stack.isEmpty() && height[i] > height[stack.peek()] ) {
	    int valley = height[stack.pop()]; // candidate valley bar
            if( !stack.isEmpty() ) // If the stack is not empty, then the candidate valley bar is a real valley bar
		result += (Math.min(height[i], height[stack.peek()]) - valley) * (i - stack.peek() - 1);
	}
	stack.push(i);
    }
    return result;
}