[Li Kou brush question] monotone stack: 84 The largest rectangle in the histogram

subject ：

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 .

 

Ideas ：

// Monotonically increasing stacks , For the column in the stack , The first column on the left whose height is less than its own is under itself

// Traverse each cylinder , If the current column height is greater than or equal to the height of the stack top column , It into the stack

// Otherwise, you will find the first column smaller than itself on the right side of the stack top element , Top of stack element , At the same time, the maximum area of the rectangle corresponding to the top element of the stack can be calculated

// Add a to the last element of the array 0, Use this condition to get all the elements in the stack out of the stack

// For special treatment on the left , If the stack is empty after an element at the top of the stack is out of the stack , It means that no element on the left is shorter than it , It is the shortest of its kind , The left side can be extended to 0

 

class Solution {
    public int largestRectangleArea(int[] heights) {
        // Monotonically increasing stacks , For the column in the stack , The first column on the left whose height is less than its own is under itself 
        // Traverse each cylinder , If the current column height is greater than or equal to the height of the stack top column , It into the stack 
        // Otherwise, you will find the first column smaller than itself on the right side of the stack top element , Top of stack element , At the same time, the maximum area of the rectangle corresponding to the top element of the stack can be calculated 
        // Add a to the last element of the array 0, Use this condition to get all the elements in the stack out of the stack 
        // For special treatment on the left , If the stack is empty after an element at the top of the stack is out of the stack , It means that no element on the left is shorter than it , It is the shortest of its kind , The left side can be extended to 0
        int[] newH = new int[heights.length + 1];
        for(int i = 0; i < heights.length;i++){
            newH[i] = heights[i];
        }
        newH[heights.length] = 0;
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for(int i = 0;i < heights.length + 1;i++){
            while(stack.size() != 0 && newH[stack.peek()] > newH[i]){
                res = Math.max(res,newH[stack.pop()] * (stack.size() == 0 ? i : (i - stack.peek() - 1))); 
            }
            stack.push(i);
        }
        return res;
    }
}