Leetcode buckle classic topic - 82 Maximum rectangle in column chart

84. The largest rectangle in the histogram

Title Description ：

 1. Violence solution

Ideas ： We only need to traverse and calculate the area of the largest rectangle with the height of each column .

It is equivalent to traversing the height of the column in turn , For each height, spread to both sides , Find out the maximum width of the rectangle with the current height .

It can be divided into two small steps ：

• Take a look on the left , See how long it can stretch to the left at most , Find the subscript of the leftmost element greater than or equal to the current column height ;
• Take a look on the right , See how long it can stretch to the right at most ; Find the subscript of the rightmost element greater than or equal to the current column height .

Operate every position , Get the area of the largest rectangle at each position , Find the maximum .

  Code implementation ：

public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 1) return heights[0];

        int maxArea = 0;
        for (int i = 0; i < len; i++) {

            int curHeight = heights[i];
            int left = i;
            // Find the largest position that can be extended on the left ( That is, it is larger than the current height )
            while (left > 0 && heights[left-1] >= curHeight)
                left--;

            // Find the largest position that can be extended on the right 
            int right = i;
            while (right < len-1 && heights[right+1] >= curHeight)
                right++;

            maxArea = Math.max(maxArea,curHeight*(right-left+1));
        }
        return maxArea;
    }

This violent solution is extremely time-consuming , The probability of running overtime , Time complexity O(n^2), Spatial complexity O(1).

2. Monotonic stack ( Add sentry ）

Optimize with monotone stack , It is typical to trade space for time , This is a little difficult to understand , Let's just look at the picture and talk .

Such as example array [2, 1, 5, 6, 2, 3],

1、 The height of the column seen at the beginning is  2 , This time with this  2  The rectangle with the maximum area of height cannot be determined , We need to continue traversing to the right .

 2. Traverse to the second column with a height of 1, Less than the height of the column at the top of the stack , Then we can know that the maximum rectangular area of the first column height is 2, And put it out of the stack , Set as dotted line for easy understanding . Then put the second column on the stack , Continue to traverse to the right .

 3. Traverse to the third column with a height of 5, We cannot determine the maximum rectangular area of the second column , therefore , Continue to stack , Traverse right .

4、 Next , Traverse to a height of  6  Cylindrical shape of , alike , In column shape  1、5、6  The maximum rectangular area for height cannot be determined .

 5. Traverse to a height of 2 When the column shape of , here The height is  6  The width of the area of the largest rectangle corresponding to the column shape of can be determined , It is clamped at a height of  5  Its column shape and height are  2  The distance between the columns of , Its height is  6, Width is  1; Set the determinable column shape as dotted line , And out of the stack .

Next, the column  5  The width of the rectangle with the corresponding maximum area can also be determined , It is clamped at a height of  1  And the height is  2  The distance between the two columns of ; When you're sure , We marked it as a dotted line and put it on the stack . 

We found a law , As long as the height of the current column is strictly smaller than that of the previous column , It must be possible to determine the maximum width of some columns before it , And the order of the determined column width is from right to left .
This phenomenon tells us , When traversing, the information to be recorded is the subscript of the traversed column , The difference between the subscripts of the two columns from left to right is the maximum width of the rectangle with the largest area .

6. When we traverse to the last height 3 When the column shape of , It is found that the maximum area of the column can not be calculated

  We can't help thinking , What about the remaining columns ？ Don't you have to calculate ？

The answer is yes, we still need to calculate ;

For this purpose, we can add two height at both ends of the input array 0 （ Or is it 0.5, Just compare 1 Strictly small ） Cylindrical shape of , You can avoid the above two classification discussions .

The two columns standing on both sides have a very vivid noun , be called sentry （Sentinel）.

With these two columns ：

1. The left column （ The first 1 It's a column ） Because it must be smaller than any element in the input array , It certainly won't come out of the stack , Therefore, the stack must not be empty , The step of determining whether the stack is empty is avoided ;

2. The column on the right （ The last column ） It is precisely because it must be smaller than any element in the input array , It will get all the elements in the input array out of the stack （ The first 1 Except for sentinel elements ）.

Here the stack corresponds to the height , In the form of monotonous increase without decrease , So called Monotonic stack （Monotone Stack）.

Let's take a look at the code and understand ：

public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 1) return heights[0];
        int[] newHeights = new int[len+2];
        // Add sentinels to the array 
        newHeights[0] = 0; // The sentry on the left 
        // Copy the old array to the location of the new array (1,len)
        System.arraycopy(heights,0,newHeights,1,len);
        newHeights[len+1] = 0;  // The sentry on the right 
        len += 2;
        Stack<Integer> stack = new Stack<>();
        stack.push(0); // Put the first sentinel into the stack first 
        int maxArea = 0;
        for (int i = 1; i < len; i++) {
            // When the height of the current column is less than the height of the column at the top of the stack , Calculate the area of the largest rectangle on the top of the stack 
            while ( newHeights[i] < newHeights[stack.peek()] ){ 
                int curHeight = newHeights[stack.pop()]; // Pop up the top column , Record his height 
                int curWidth = i - stack.peek() -1;

                maxArea = Math.max(maxArea,curHeight*curWidth);
            }
            stack.push(i);
        }
        return maxArea;

Complexity analysis ： Time complexity O(n), An element can be stacked at most once , Once out of the stack ;

Spatial complexity O(n), It depends on the space of the stack .

summary ： From method 1 to method 2 , Monotone stack ( The way of adding sentinels ) The way to optimize , Space for time .

notes ： The monotonic stack method is used in many places , It is suggested to study repeatedly , I have listed some problems solved by monotone stack ：