Date: 2024.04.20
lc 84. 柱状图中最大的矩形
// 单调栈
class Solution {
public:
int largestRectangleArea(vector& heights) {
// 对于每个柱子,我们考虑按当前柱子进行中心扩散,直到找到其左侧及其右侧,高度小于该柱子的柱子为止。
// 例如当前柱子高度为2,则所有高度大于等于2的柱子都可以加入该柱子为高的矩形。
// 因此,我们需要找到左侧和右侧第一个高度小于指定高度的柱子。(则范围内均为大于等于该高度的柱子)
int n = heights.size();
vector leftIdx(n, 0);
vector rightIdx(n, 0);
// 我们借助单调栈获取左右第一个高度小于指定高度的数。
// 要获取左侧最近较小值,我们维护一个单调递增的栈。每当一个元素要入栈,我们舍去栈顶的大于该元素的值。
// 若栈不为空,则此时的栈顶,即为该元素的左侧第一个更小值。若栈为空,则左侧第一个更小值视作0.
stack st;
for(int i=0; i heights[st.top()]){
leftIdx[i] = st.top();
}
else if(!st.empty() && cur_height <= heights[st.top()]){
while(!st.empty() && cur_height <= heights[st.top()]){
st.pop();
}
if(st.empty()){
leftIdx[i] = -1;
}
else{
leftIdx[i] = st.top();
}
}
else if(st.empty()){
leftIdx[i] = -1;
}
st.push(i);
}
while(!st.empty()){
st.pop();
}
for(int i=n-1; i>=0; i--){
int cur_height = heights[i];
if(!st.empty() && cur_height > heights[st.top()]){
rightIdx[i] = st.top();
}
else if(!st.empty() && cur_height <= heights[st.top()]){
while(!st.empty() && cur_height <= heights[st.top()]){
st.pop();
}
if(st.empty()){
rightIdx[i] = n;
}
else{
rightIdx[i] = st.top();
}
}
else if(st.empty()){
rightIdx[i] = n;
}
st.push(i);
}
int max_area = -1;
for(int i=0; i& heights) {
int max_area = INT_MIN;
int n = heights.size();
// 遍历起点和终点,矩形高为所有点中min,宽为(终点-起点+1);
for(int start = 0; start < n; start++){
int cur_min = heights[start];
for(int end = start; end < n; end++){
cur_min = min(cur_min, heights[end]);
int cur_area = (end - start + 1) * cur_min;
max_area = max(max_area, cur_area);
}
}
return max_area;
}
};