84. 柱状图最大矩形
题目描述
输入非负整数数组 heights，表示一张柱状图。第 i 根柱子宽 1、高 heights[i]，相邻柱子紧挨着。
在柱状图范围内画一个边与坐标轴平行的矩形，矩形必须完全落在柱子内部。
返回这种矩形的最大面积。
示例 1
输入：heights = [2,1,5,6,2,3] 输出：10
解释：取高为 5 和 6 的两根柱子，以高度 5 画矩形，面积 5 * 2 = 10。
示例 2
输入：heights = [2,4] 输出：4
解释：只取高为 4 的柱子得 4，两根一起只能高 2，面积也是 4。
数据范围
1 <= heights.length <= 10^50 <= heights[i] <= 10^4
解题思路
单调递增栈结算矩形。
为什么正确
栈内下标递增、高度单调不减；弹出柱子时，当前索引是右侧第一个更矮位置，剩余栈顶确定可用左边界。
复杂度分析
时间 O(n)，额外空间 O(n)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def largestRectangleArea(self,a):
st=[];best=0
for i,h in enumerate(a+[0]):
while st and a[st[-1]]>h:
j=st.pop();l=st[-1]+1 if st else 0;best=max(best,a[j]*(i-l))
st.append(i)
return bestclass Solution {
public int largestRectangleArea(int[] a) {
Deque<Integer> st = new ArrayDeque<>(); int best = 0, n = a.length;
for (int i = 0; i <= n; i++) {
int h = i < n ? a[i] : 0;
while (!st.isEmpty() && a[st.peek()] > h) {
int j = st.pop();
int l = st.isEmpty() ? 0 : st.peek() + 1;
best = Math.max(best, a[j] * (i - l));
}
st.push(i);
}
return best;
}
}class Solution {
public:
int largestRectangleArea(vector<int>& a) {
vector<int> st; int best = 0, n = a.size();
for (int i = 0; i <= n; i++) {
int h = i < n ? a[i] : 0;
while (!st.empty() && a[st.back()] > h) {
int j = st.back(); st.pop_back();
int l = st.empty() ? 0 : st.back() + 1;
best = max(best, a[j] * (i - l));
}
st.push_back(i);
}
return best;
}
};func largestRectangleArea(a []int) int {
st, best, n := []int{}, 0, len(a)
for i := 0; i <= n; i++ {
h := 0
if i < n {
h = a[i]
}
for len(st) > 0 && a[st[len(st)-1]] > h {
j := st[len(st)-1]; st = st[:len(st)-1]
l := 0
if len(st) > 0 {
l = st[len(st)-1] + 1
}
best = max(best, a[j]*(i-l))
}
st = append(st, i)
}
return best
}var largestRectangleArea = function(a) {
const st = []; let best = 0; const n = a.length;
for (let i = 0; i <= n; i++) {
const h = i < n ? a[i] : 0;
while (st.length && a[st[st.length - 1]] > h) {
const j = st.pop();
const l = st.length ? st[st.length - 1] + 1 : 0;
best = Math.max(best, a[j] * (i - l));
}
st.push(i);
}
return best;
};function largestRectangleArea(a: number[]): number {
const st: number[] = []; let best = 0; const n = a.length;
for (let i = 0; i <= n; i++) {
const h = i < n ? a[i] : 0;
while (st.length && a[st[st.length - 1]] > h) {
const j = st.pop()!;
const l = st.length ? st[st.length - 1] + 1 : 0;
best = Math.max(best, a[j] * (i - l));
}
st.push(i);
}
return best;
};