84. Largest Rectangle in Histogram

Question

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.

Example:

Input: [2,1,5,6,2,3]
Output: 10

Thinking:

Method 1: 分析：
1. 如果完全是递增的[1,2,3,4,5,6],我们的结果是
  - heights[i] * (size - i)其中的最大值，这个公式的意思是每次取最小的高度，向右扩展成长方形。
2. 如果不是完全递增的，我们需要构造成递增的序列：
  - 如果出现了下降，我们取出栈中的比当前值小的所有值，并替换成当前值。
  - 此时我们要更新最大值，例如5,6，我们让6出栈，并且尝试更新最大值为6，我们再让5出栈，尝试更新最大值为5 * 2。
  - 到最后栈中的所有元素都是递增的，我们使用step1的方法更新最大值。

class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights == null || heights.length == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        int len = heights.length;
        stack.push(heights[0]);
        int result = 0;
        int count = 0;
        for(int i = 1; i < len; i++){
            int add = heights[i];
            if(add >= stack.peek())
                stack.push(heights[i]);
            else{
                count = 0;
                while(!stack.isEmpty() && stack.peek() > add){
                    count++;
                    int val = stack.pop();
                    result = Math.max(result, val * count);
                }
                while(count != 0){
                    count--;
                    stack.push(add);
                }
                stack.push(add);
            }
        }
        count = 1;
        while(!stack.isEmpty()){
            int last = stack.pop();
            result = Math.max(result, last * count++);
        }
        return result;
    }
}

Second time

Monostack ```Java /** [0,1,2,3,4,5] [2,1,5,6,2,3] action stack(save the index) area max
2 add to stack 2 0 0
1 pop 2 1 2 2
5 add to stack 1, 5 2 2
6 add to stack 1, 5, 6 2 2
2 pop 6 from stack 1, 5 6 6 pop 5 from stack 1 10 10 add 2 to stack 1, 2 0 0
3 add 3 to stack 1, 2, 3 0 0
0 pop 3 from stack 1, 2 3 10 pop 2 from stack 1 4 10 pop 1 from stack empty 6 10 */ class Solution { public int largestRectangleArea(int[] heights) { if(heights == null || heights.length == 0) return 0; int res = 0; Stack stack = new Stack<>(); for(int i = 0; i <= heights.length; i++){ int h = i == heights.length ? 0: heights[i]; // add a 0 to the last so we have a chance to deal with the last mono inscrease part. while(!stack.isEmpty() && h < heights[stack.peek()]){ // pop the value larger than current one to keep the monostack. int height = heights[stack.pop()]; int index = stack.isEmpty() ? -1: stack.peek(); // if empty, means current value is the minimum res = Math.max(res, height * (i - index - 1)); // get the local area } stack.push(i); // always add current index to the stack. } return res; } } ```

Reference

Leetcode : 84. Largest Rectangle in Histogram 讲解