题目
84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：

输入： heights = [2,4]
输出： 4
提示：
- 1 <= heights.length <=105
- 0 <= heights[i] <= 104
我的代码（Python）
/**
* @param {number[]} heights
* @return {number}
*/
var largestRectangleArea = function(heights) {
if (heights.length === 0) {
return 0;
}
let calResult = new Array(heights.length).fill(0);
let calStack = [];
// right
for (let i = 0; i < heights.length; i++) {
calResult[i] = heights[i];
while (calStack.length > 0 && heights[calStack[calStack.length - 1]] > heights[i]) {
calResult[calStack[calStack.length - 1]] += heights[calStack[calStack.length - 1]] * (i - calStack[calStack.length - 1] - 1);
calStack.pop();
}
if (heights[i] > 0) {
calStack.push(i);
}
}
for (let idx of calStack) {
calResult[idx] += heights[idx] * (heights.length - 1 - idx);
}
calStack = [];
// left
for (let i = heights.length - 1; i >= 0 ; i--) {
while (calStack.length > 0 && heights[calStack[calStack.length - 1]] > heights[i]) {
calResult[calStack[calStack.length - 1]] += heights[calStack[calStack.length - 1]] * (calStack[calStack.length - 1] - i - 1);
calStack.pop();
}
if (heights[i] > 0) {
calStack.push(i);
}
}
for (let idx of calStack) {
calResult[idx] += heights[idx] * idx;
}
let result = 0;
for (let i = 0; i < calResult.length; i++) {
result = Math.max(result, calResult[i]);
}
return result;
};点评
要找的是每一个数，对应的左右两边比它小的最近一个索引。这样就可以计算面积了。
用栈的思想分别找左右边界。
参考739. 每日温度
我的解法
官方的基本解法就是这样。不过在弹出时，就可以确定另一侧的边界，所以只遍历一次就可以了，这个是我没想到的，差一些的原因应该就是这个。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog