AcWing 131. (单调栈)直方图中最大的矩形
原题链接
简单
作者:
Avetre
,
2024-11-30 11:53:12
,
所有人可见
,
阅读 2
思路
用一个单调递增栈
保存当前位置左侧的
、高度小于等于当前位置柱子高度
的位置索引
。找最大矩形面积即找以各柱子高度为高的最大矩形面积中的最大值。遍历整个高度数组,对于以当前柱子高度为高的矩形,最大面积即为最大横坐标跨度,左边界索引为stk[top-1]
(栈单增,stk[top-1]是左边第一个高度小于或等于栈顶元素的位置),右边界索引为i-1
(i是第一个比栈顶元素矮的柱子,故i-1是最后一个高度大于或等于栈顶元素的位置),对于每个弹出的栈顶元素,使用其高度和上述计算的宽度来计算面积,并更新记录的最大面积
注意
1.数据溢出
2.遍历完直方图时,栈中可能还有剩余元素需要处理
3.每轮需初始化重置栈和最大面积
4.只在栈顶元素出栈时更新最大面积(出栈说明右边界已找到或已遍历至末尾,而左边界由单调栈保存,此时计算的面积才是以各柱高为高的最大矩形面积)
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long int square[N], stk[N], top = 0;
// 存储矩形最大面积 注意数据溢出
long long int S = 0;
int main()
{
int n;
while (1)
{
cin >> n;
// 结束输入
if (n == 0)
break;
for (int i = 1; i <= n; i++)
{
scanf("%d", &square[i]);
// 单调递增栈 存储下标
// 如果当前矩形高度小于栈顶矩形高度 弹出栈顶元素 计算以栈顶元素为高度的最大面积(长度为i-1-stk[top-1])
// 分析长度为i-1-stk[top-1]:
// 栈顶元素的右边界是 i - 1(因为 i 是第一个比栈顶元素矮的柱子,所以 i - 1 是最后一个高度大于或等于栈顶元素的位置)
// 栈顶元素的左边界是 stk[top - 1](因为栈是单调递增的,所以 stk[top - 1] 是左边第一个高度小于或等于栈顶元素的位置)
while (top && square[stk[top]] >= square[i])
{
S = S >= (i - 1 - stk[top - 1]) * square[stk[top]] ? S : (i - 1 - stk[top - 1]) * square[stk[top]];
top--;
}
stk[++top] = i;
}
// 处理栈中剩余元素
while (top)
{
S = S >= (n - stk[top - 1]) * square[stk[top]] ? S : (n - stk[top - 1]) * square[stk[top]];
top--;
}
cout << S << endl;
// 重置以便下轮循环使用
top = 0;
S = 0;
}
return 0;
}