84. Largest Rectangle in Histogram.md

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

1. Monostack

/**
[0,1,2,3,4,5]
[2,1,5,6,2,3]
                            action                  stack(save the index)           area            max
1. 2                        add to stack                2                           0               0    
2. 1                        pop 2                       1                           2               2
3. 5                        add to stack               1, 5                         2               2
4. 6                        add to stack              1, 5, 6                       2               2
5. 2                        pop 6 from stack          1, 5                          6               6
                            pop 5 from stack            1                           10              10
                            add 2 to stack            1, 2                          0               0
6. 3                        add 3 to stack            1, 2, 3                       0               0
7. 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<Integer> 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

1. Leetcode : 84. Largest Rectangle in Histogram 讲解