【代码随想录】54
2023年11月7日 单调栈3
84. 柱状图中最大的矩形
找到两边比其小的第一个元素
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
vector<int> minLeftIndex(heights.size());
vector<int> minRightIndex(heights.size());
int size = heights.size();
// 记录每个柱子 左边第一个小于该柱子的下标
minLeftIndex[0] = -1; // 注意这里初始化,防止下面while死循环
for (int i = 1; i < size; i++) {
int t = i - 1;
// 这里不是用if,而是不断向左寻找的过程
while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
minLeftIndex[i] = t;
}
// 记录每个柱子 右边第一个小于该柱子的下标
minRightIndex[size - 1] = size; // 注意这里初始化,防止下面while死循环
for (int i = size - 2; i >= 0; i--) {
int t = i + 1;
// 这里不是用if,而是不断向右寻找的过程
while (t < size && heights[t] >= heights[i]) t = minRightIndex[t];
minRightIndex[i] = t;
}
// 求和
int result = 0;
for (int i = 0; i < size; i++) {
int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
result = max(sum, result);
}
return result;
}
};