<> Monotone stack
We start with force buckle 84 The idea of solving the problem leads to the concept of monotone stack , First look at the buckle 84 The title of the question is described below ：
On violence
： This problem is to find the largest and rectangular area , The solution to violence is ： Based on each column , Find the largest rectangular area containing the column . That is, when traversing each column , Look at its height , Rectangle with the largest width . This approach is very simple , But the time complexity of traversing the column is O(N), The time complexity of finding the maximum width of the rectangle containing each column is also high O(N), In this way, the total time complexity of the algorithm is O(N^2)
Improvement of algorithm ： Can the time complexity of the problem be reduced to O(N)? That is, we try to solve the problem by traversing all columns at once .
The key to the problem is to find a second one i The maximum width of a rectangle whose height is the height of a column , That is to find the left bound and bounded bound of a location index not greater than this height .
Search for the right boundary
： The right boundary can be found by direct traversal , Suppose there is a stack , For section i A pillar , We want to find its right boundary , Then there are two possibilities , That is, the next column on its right is smaller than it , Then the next column becomes its right boundary ; And if the next column is higher than him , Then its right boundary is still unknown . until , Hit a column smaller than it , Then the position of the column becomes its right boundary .
*
The search process of the right boundary can be embodied as a stack operation ： That is, when the stack is empty , Stack the traversed columns , When the next traversed column is higher than the column at the top of the stack , At this time, no right boundary of any column can be determined , So keep pushing ; When the traversed column is lower than the column at the top of the stack , Then the right boundary of the stack top column is determined . Calculate the width of the stack top element out of the stack , Then see if the new stack top element will be determined as the right boundary due to the appearance of the traversed column just now , That is, compare the height of the new stack top column and the traversed column , Repeat the above operation .
On the search of left boundary
： The left bound can be a cumulative , That is, elements larger than it can be accumulated into the length of the left boundary , It can also be a record , Record the position of the number smaller than it on the left . Operation based on the above stack , If you want to record the position of the first column smaller than it on the left , There are two cases , If it is not the last element in the stack , Then the position of the smaller element under it is its left boundary , If it is already the last element in the stack , Note that all the previous elements are larger than it , It's all out of the stack in front of it , So its left bound can extend to the front of the array .
Concept of monotone stack
： Firstly, monotone stack is a data structure of stack type , Have all the basic operations that the stack has . The special feature of monotone stack is that it conforms to such characteristics ： The order of the elements in the stack from the bottom of the stack to the top of the stack is monotonous and orderly , If from the bottom of the stack to the top of the stack , Monotonic decreasing of elements , We call it incremental stack , Because when it comes out of the stack , The order of elements is increasing ; If the element is incremented from the bottom of the stack to the top of the stack , Then it is called decrement stack .
Monotone stack must maintain monotonicity when entering the stack , If the element to be stacked does not conform to monotonicity , Then we pop up the top element of the stack , Until the stack element can meet the monotonicity after being stacked . Take monotonically decreasing stack as an example , The elements added to the stack are 1
2 5 4, So the first three elements 1 2 5
Can be directly stacked , But when the element 4 When you are about to stack , You will find the top element of the stack 5 Greater than the stacked element 4, So we have to 5 Out of stack , Then find the new stack top element at this time 2 less than 4, Then it can be stacked at this time .
int stack[1000000]; int top=0; void push(int index) { stack[top++]=index; } int
Pop() { return stack[--top]; } int Top() { return stack[top-1]; } int isEmpty()
{ if(top==0) return 1; else return 0; } int largestRectangleArea(int* heights,
int heightsSize){ int i=0,max=0,temp=0,pre=0; while(i<heightsSize) { if(isEmpty(
)||heights[Top()]<=heights[i]) { push(i++); } else{ if(top==1) { temp=i*heights[
Pop()]; if(max<temp) max=temp; } else{ temp=(i-stack[top-2]-1)*heights[Pop()];
if(max<temp) max=temp; } } } while(!isEmpty()) { if(top==1) { temp=i*heights[Pop
()]; if(max<temp) max=temp; } else{ temp=(i-stack[top-2]-1)*heights[Pop()]; if(
max<temp) max=temp; } } return max; }
With the above analysis , The algorithm based on monotone stack is very simple .
We iterate through the elements of the array one by one , If the stack is empty or not less than the top element of the stack, it will be put on the stack , Otherwise, the top element of the stack will be out of the stack , Calculate the rectangular area based on the column while out of the stack , That is, the width formed between the left and right boundaries is multiplied by the height of the rectangle .（ Judge when calculating the width between the left and right boundaries , See whether the element of the stack is the element at the bottom of the stack ）
After traversal , If there are elements in the stack , Then the stack area is calculated in turn , Finally, update the result to the maximum area .
Technology