84. 柱状图中最大的矩形

思路一：暴力法

思路参考：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/

枚举每个柱子为高度的最大矩形的面积

实现：对每个高度的柱子向两边扩张，试图寻找以当前高度为矩形的最大宽度

 1 class Solution {
 2     public int largestRectangleArea(int[] heights) {
 3         
 4         // 对每个高度的柱子向两边扩张，试图寻找以当前高度为矩形的最大宽度
 5         int maxArea = 0;
 6         int len = heights.length;
 7         for(int i = 0; i < len; i++){
 8             int leftBorder = i-1;
 9             for(; leftBorder >= 0 && heights[leftBorder] >= heights[i]; leftBorder--);
10             int rightBorder = i+1;
11             for(; rightBorder < len && heights[rightBorder] >= heights[i]; rightBorder++);
12             maxArea = Math.max(maxArea, heights[i] * (rightBorder - leftBorder - 1));
13         }
14         return maxArea;
15     }
16 }

leetcode 执行用时：938 ms > 19.41%, 内存消耗：40.2 MB > 40.10%

复杂度分析：

时间复杂度：O(n²)。双层for循环，所以时间复杂度为O(n²)。

空间复杂度：O(1)。

思路二：递减栈

递减栈，从栈顶到栈底的序列是一个降序序列，递减 如果当前高度大于栈顶下标对应的高度，直接入栈，否则循环出栈，直至当前高度大于栈顶高度或者栈为空，每次出栈一个元素，用当前下标减去出栈下标再减一，得到宽度，乘以出栈下标对应的元素，得出面积 计算宽度,如果栈为空，左边界为0，右边界为i,  否则左边界为栈顶下标，右边界为数组长度 一次遍历之后，出栈栈中剩余元素， 出栈过程中如果当前出栈的元素等于栈顶下标对应的元素，持续出栈，直到栈顶下标元素小于当前元素的下标为止，因为高度相等的话只需要统计最左边的柱子和他的宽度即可，中间的没必要统计，因为都一样。 如果栈为空，左边界为0， 否则左边界为栈顶下标，右边界为数组长度

 1 class Solution {
 2     public int largestRectangleArea(int[] heights) {
 3     
 4         Stack<Integer> stack = new Stack<>();
 5         int len = heights.length;
 6         int maxArea = 0;
 7         for(int i = 0; i < len; i++){
 8             // 如果当前高度大于栈顶下标对应的高度，直接入栈，否则循环出栈，直至当前高度大于栈顶高度或者栈为空
 9             while(!stack.isEmpty() && heights[i] < heights[stack.peek()]){
10                 int index = stack.pop();   
11                 int width = 0;
12                 // 计算宽度,如果栈为空，左边界为0，右边界为i,  否则左边界为栈顶下标，右边界为数组长度
13                 if(stack.isEmpty()){
14                     width = i;
15                 }else{
16                     width = i - stack.peek() - 1;
17                 }
18                 maxArea = Math.max(maxArea, width * heights[index]);
19             }
20             stack.push(i);
21         }
22         // 一次遍历之后，出栈栈中剩余元素，
23         while(!stack.isEmpty()){
24             int index = stack.pop();
25             // 出栈过程中如果当前出栈的元素等于栈顶下标对应的元素，
26             // 持续出栈，直到栈顶下标元素小于当前元素的下标为止
27             while(!stack.isEmpty() && heights[stack.peek()] == heights[index]){
28                 stack.pop();
29             }
30             int width = 0;
31             // 如果栈为空，左边界为0， 否则左边界为栈顶下标，右边界为数组长度
32             if(stack.isEmpty()){
33                 width = len;
34             }else{
35                 width = len - stack.peek() - 1;
36             }
37             maxArea = Math.max(maxArea, width * heights[index]);
38         }
39         return maxArea;
40     }
41 }

leetcode 执行用时：12 ms > 71.41%, 内存消耗：39.9 MB > 63.66%

复杂度分析：

时间复杂度：O(n)。每个元素下标最多只被入栈一次以及出栈一次，所以 时间复杂度为O(n)。

空间复杂度：O(n)。空间花费取决于栈的大小，栈的大小最大为O(n-1), 即当heights[]数组递增排列时，所有元素的下标都会入队，所以空间复杂度为O(n)。