题目
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
思路一
这里先介绍暴力解法，后续优化版将基于暴力解法为基础，先依次遍历每个木块，对于木块 i，我们分别向前向后查找高度小于木块 i，得到下标 left, right，然后计算 (right-left-1)*heights[i] 就能计算以木块 i 为“中心”的最大矩形面积，再取循环中的最大值即为答案；
代码一
class Solution {
public int largestRectangleArea(int[] heights
) {
int len
= heights
.length
, ans
= 0;
for (int i
=0; i
<len
; i
++){
int left
= i
, right
= i
;
while (left
>= 0 && heights
[left
] >= heights
[i
])
left
--;
while (right
< len
&& heights
[right
] >= heights
[i
])
right
++;
ans
= Math
.max(ans
, heights
[i
]*(right
-left
-1));
}
return ans
;
}
}
思路二
思路一中，外面一层 for 循环加内层的 while 循环，时间复杂度为
O
(
N
2
)
O(N^2)
O(N2)，外层循环肯定是没法优化的，那么内层的 while 循环呢？我们直到 while 循环的目的是找到高度小于木块 i 的木块的下标，那么要是能在常熟时间复杂度内找到这两个下标，时间复杂度就能提升到
O
(
N
)
O(N)
O(N)；
这里参考了题解，用 单调栈 的思想，我们将木块依次入栈，假如木块 i 大于等于栈顶木块高度，则直接入栈，假如木块 i 高度小于栈顶木块高度，那么对于栈顶木块来说，木块 i 就是它的右边最近的高度小于它的的木块，那么左边的高度小于它的木块，就是栈顶的第二个木块，这就是单调栈的精髓所在，具体可详细参考代码：
代码二
class Solution {
public int largestRectangleArea(int[] heights
) {
int len
= heights
.length
+2, ans
= 0;
int[] copy
= new int[len
];
System
.arraycopy(heights
, 0, copy
, 1, len
-2);
Deque
<Integer> stack
= new ArrayDeque<>();
for (int i
=0; i
<len
; i
++){
while (!stack
.isEmpty() && copy
[i
] < copy
[stack
.peek()]){
int t
= stack
.pop();
ans
= Math
.max(ans
, copy
[t
]*(i
-stack
.peek()-1));
}
stack
.push(i
);
}
return ans
;
}
}
