Sword finger offer II 039 Maximum rectangular area of histogram

Summary

Monotonic stack , It's hard to think .

subject

Given an array of nonnegative integers heights , The numbers in the array are used to represent 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 .

link ：https://leetcode.cn/problems/0ynMMM

Ideas

Or use monotone stack . You'll find that , The core of these questions , All use a monotonous stack , Then when traversing the array , Compare the current element with the top element , Always ensure that the top element of the stack is the largest （ Or the smallest ）.

The core points of solving this problem are as follows ：

1. Centered on the height of a column , Spread to both sides to find the boundary . Find a pillar shorter than this one , It's the boundary . At this time, the area can be calculated according to the height of the column and the boundary length .
2. Use a monotonic stack whose top is larger than the bottom , To maintain the left boundary .
   1. If the current element traversed is larger than the top element , The stack .
   2. If the current element traversed is smaller than the top element , Then the top element of the stack is column , And the position of the current element , Is the rightmost boundary . And because it's a monotonous stack , So the elements below the top of the stack , When the top of the stack is a column , The rightmost boundary .
   3. Push stack out of stack , Compare the size relationship between the new stack top and the current element , Repeat the logic of the first two
3. Traversal complete , Then put the elements that still exist in the stack , Do further calculations . Only when the rightmost column is higher than the front column , That's what happens . So the right boundary at this time , Is the right boundary of the array .

solution ： Monotonic stack

Code

public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    //  It is convenient to deal with boundary problems 
    stack.push(-1);
    int result = 0;
    for (int i = 0; i < heights.length; i++) {
        int current = heights[i];
        while (stack.peek() != -1 && heights[stack.peek()] > current) {
            //  Get the subscript of the top of the stack element and remove the top of the stack element 
            int height = heights[stack.pop()];
            int with = i - stack.peek() - 1;
            result = Math.max(result, height * with);
        }
        stack.push(i);
    }
    //  Handle the remaining boundaries in the stack . At this time, the right boundary must be the rightmost end of the array 
    while (stack.peek()!=-1) {
        result = Math.max(result, heights[stack.pop()] * (heights.length - stack.peek() - 1));
    }
    return result;
}

Submit results

P.S. The animation of this solution is great ：https://leetcode.cn/problems/0ynMMM/solution/hua-luo-yue-que-wo-zhen-de-zhen-de-nu-li-ohjt/