LC Container With Most Water/Trapping Rain Water/Largest Rectangle in Histogram

###Task1 Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

histogram

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

histogram

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Have you met this question in a real interview? Yes Example Given height = [2,1,5,6,2,3], return 10.

###java

public class Solution {
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    public int largestRectangleArea(int[] height) {
        // write your code here
        if (height == null || height.length == 0) {
            return 0;
        }
        int N = height.length;
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i <= N; i++) {
            int cur = i == N ? -1 : height[i];
            while (!stack.isEmpty() && cur < height[stack.peek()]) {
                int h = height[stack.pop()];
                int w = stack.isEmpty() ? i : (i - stack.peek() - 1);
                max = Math.max(max, h * w);
            }
            stack.push(i);
        }
        return max;
    }
}

###Points

• Tricky way to use stack.
• Maintain an increasing height in the stack, once get a height less than the top of stack, keep poping(computing area at same time) until the increasing order remains.

###Task2 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.

For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

###Python

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if len(height) == 0:
            return 0
        left = [0 for i in range(len(height))]
        right = [0 for i in range(len(height))]

        left[0] = height[0]
        right[-1] = height[-1]
        for i in range(1, len(height)):
            left[i] = max(left[i - 1], height[i])
            right[-1 - i] = max(right[-i], height[-1 - i])
        ret = 0
        for i in range(len(left)):
            ret += min(left[i], right[i]) - height[i]
        return ret
        

###Points

• Two iteration from both side: find the min height from both side;
• current point water = min(left[i], right[i]) - height[i]

###Task3 Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

###java

public class Solution {
    public int maxArea(int[] height) {
        int length = height.length;
        if (length < 2) {
        	return 0;
        }
        int left = 0;
        int right = length -1;
        int max = 0;
        while (left < right) {
        	max = Math.max(max, (right - left) * Math.min(height[left], height[right]));
        	if (height[left] < height[right]) {
        		left++;
        	} else {
        		right--;
        	}
        }
        return max;
    }
}

###Points

• Two pointers.