Monotonic stack -84 The largest rectangle in the histogram

1. subject

Inherent 42. Rainwater collection Almost the same , It is suggested to combine the two

Given n Nonnegative integers , It is used to indicate the height of each column in the histogram . Each column is adjacent to each other , And the width is 1 .

In this histogram , The maximum area of a rectangle that can be outlined .

Example 1:

 Input ：heights = [2,1,5,6,2,3]
 Output ：10
 explain ： The largest rectangle is the red area in the figure , Area is  10

Example 2：

 Input ： heights = [2,4]
 Output ： 4

 source ： Power button （LeetCode）
 link ：https://leetcode.cn/problems/largest-rectangle-in-histogram

2. Their thinking

Solution 1 ： Dynamic programming

Understand through the topic , It is the two pillars that require the most （ It can also be a single column ） The largest area of , We can consider using dynamic programming

and 42. The question of rain is somewhat similar , The difference is , This problem needs to find the index of the column smaller than the left and right of the current column , So what needs to be recorded is the index

Method 2 ： Monotonic stack

This topic and 42. The topic of receiving rainwater corresponds to , Receiving rainwater requires that the elements in the stack be sorted from large to small , then , Take the top of the stack, the next element at the top of the stack, and the three elements to be put into the stack to receive water ！ This problem requires that the elements in the stack be sorted from small to large , Again , The top of the stack and the next element at the top of the stack, as well as the three elements to be put into the stack, will receive water ！

Then analyze three situations ：

The rest is to analyze the following three situations ：

• Situation 1 ： Current traversal elements heights[i] Less than the top of the stack element heights[st.top()] The situation of （ The largest area appears ）
• Situation two ： Current traversal elements heights[i] Equal to the top element of the stack heights[st.top()] The situation of
• Situation three ： Current traversal elements heights[i] Greater than the top element of the stack heights[st.top()] The situation of

3. Code

Method 1 ： Dynamic programming

public int largestRectangleArea(int[] heights) {
    
        int length = heights.length;
        int[] minLeftIndex = new int [length];
        int[] maxRigthIndex = new int [length];
        //  Record the first subscript on the left that is smaller than the column 
        minLeftIndex[0] = -1 ;
        for (int i = 1; i < length; i++) {
    
            int t = i - 1;
            //  This is not for if, But the process of constantly looking to the right 
            while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
            minLeftIndex[i] = t;
        }
        //  Record each column   The first one on the right is smaller than the subscript of the column 
        maxRigthIndex[length - 1] = length;
        for (int i = length - 2; i >= 0; i--) {
    
            int t = i + 1;
            while(t < length && heights[t] >= heights[i]) t = maxRigthIndex[t];
            maxRigthIndex[i] = t;
        }
        //  Sum up 
        int result = 0;
        for (int i = 0; i < length; i++) {
    
            int sum = heights[i] * (maxRigthIndex[i] - minLeftIndex[i] - 1);
            result = Math.max(sum, result);
        }
        return result;
    }

Method 2 ： Monotonic stack

int largestRectangleArea(int[] heights) {
    
        Stack<Integer> st = new Stack<Integer>();
        
        //  Array capacity , Add an element to the head and tail 
        int [] newHeights = new int[heights.length + 2];
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;
        for (int index = 0; index < heights.length; index++){
    
            newHeights[index + 1] = heights[index];
        }

        heights = newHeights;
        
        st.push(0);
        int result = 0;
        //  The first element is already on the stack , From the subscript 1 Start 
        for (int i = 1; i < heights.length; i++) {
    
            //  Be careful heights[i]  Is and heights[st.top()]  Compare  ,st.top() It's a subscript 
            if (heights[i] > heights[st.peek()]) {
    
                st.push(i);
            } else if (heights[i] == heights[st.peek()]) {
    
                st.pop(); //  This can be added , Can not add , The effect is the same , Different ideas 
                st.push(i);
            } else {
    
                while (heights[i] < heights[st.peek()]) {
     //  Note that while
                    int mid = st.peek();
                    st.pop();
                    int left = st.peek();
                    int right = i;
                    int w = right - left - 1;
                    int h = heights[mid];
                    result = Math.max(result, w * h);
                }
                st.push(i);
            }
        }
        return result;
    

4. performance

Method 1 ： Dynamic programming

• Time complexity ：O(n)
• Spatial complexity ：O(n)

Method 2 ： Monotonic stack

• Time complexity ：O(n)
• Spatial complexity ：O(n)