当前位置：首页 > news >正文

【单调栈】-----【Largest Rectangle in a Histogram】

news 2025/6/22 17:22:31

Largest Rectangle in a Histogram

题目链接

题目描述

如图所示，在一条水平线上有 $n$ 个宽为 $1$ 的矩形，求包含于这些矩形的最大子矩形面积（图中的阴影部分的面积即所求答案）。

输入格式

有多组测试数据，每组数据占一行。输入零时读入结束。

每行开头为一个数字 $n(1\le n\le 10^5)$ ，接下来在同一行给出 $n$ 个数字 $h_1,h_2,\cdots, h_n (0\le h_i\le 10^9)$ ，表示每个矩形的高度。

输出格式

对于每组数据，输出最大子矩阵面积，一组数据输出一行。

输入输出样例 #1

输入 #1

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

输出 #1

8
4000

题解：（单调栈）

单调栈原理见本文

一、问题抽象

我们的问题可以等价于：

在一个由高度数组构成的柱状图中，寻找一个连续子区间，使得该区间中所有柱子的高度都不小于某个最小值 $h$ ，从而形成面积最大的矩形区域。

观察发现：

以任意一根柱子为最低高度，我们可以向两边尽量扩展，直到遇到比它低的柱子为止。形成的就是以该柱子为高的最大矩形。
所以，我们可以尝试以每一根柱子为核心，求出它能扩展的最大左右边界。

对于每根柱子 $i$ ：

左边界：找到最靠近它、且高度小于它的柱子下标，记作 $L_i$ 。
右边界：找到最靠近它、且高度小于它的柱子下标，记作 $R_i$ 。

那么，以第 $i$ 根柱子为高的最大矩形面积为：

$\text{面积}_i = h_i \times (R_i - L_i - 1)$

最终取所有面积的最大值即可。

二、传统方法的局限

朴素做法是：枚举每根柱子，暴力向左和向右遍历找边界，这样每根柱子的左右边界查找都是 $O (n)$ 的，总体时间复杂度是：

$O(n^2)$

这在 $\leq 10^5$ 的数据下必然超时。

三、优化技巧：单调栈

我们可以用单调栈在 $O (n)$ 的时间内找出每根柱子的左右边界：

对于左边界，从左往右遍历，栈中保持高度递增。
对于右边界，从右往左遍历，栈中同样保持高度递增。

单调栈的本质：维护候选区间端点的一组位置下标，利用高度单调性，快速排除不符合条件的下标，从而高效求得边界。

注意点：

当某一侧无更矮柱子时，用越界值替代（左边记作 0，右边记作 n+1），确保计算宽度时逻辑统一。

四、算法实现步骤详解

1. 找左边界函数 `lii`

目标：对每个柱子 $i$ ，找到左边第一个 $h_i$ 的柱子。
维护一个单调递增栈（栈中存的是下标，满足高度递增）。
遍历每根柱子时：
- 不断弹出栈中比当前柱子高或等高的下标；
- 若栈为空，说明左边没有更矮柱子，设置边界为 0；
- 否则边界为栈顶元素下标。

2. 找右边界函数 `rii`

同理，从右往左遍历柱子。
使用单调递增栈，保持右边更矮柱子在栈顶。
若右侧无更矮柱子，边界设为 n+1（数组越界后的位置）。

3. 计算最大矩形面积

遍历每根柱子，设其高度为 $h_i$ ，左右边界为 $L_i$ 和 $R_i$ ；
则以 $h_i$ 为高的矩形宽度为： $R_i - L_i - 1$ ；
更新当前最大面积。

五、完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long// 函数 lii 用于计算每个柱子左侧第一个高度小于它的柱子位置（单调栈实现）
vector<int> lii(const vector<int>& nums, int n)
{// 单调栈，存放柱子下标，栈内保持对应高度递增（严格递增）stack<int> li;// ans[i] 表示第 i 根柱子左侧第一个比它矮的柱子位置，若无则为 0                vector<int> ans(n + 1, 0);   // 从左到右遍历每根柱子for (int i = 1; i <= n; i++){// 1.当栈顶柱子高度 >= 当前柱子高度，说明栈顶柱子无法成为左侧第一个更矮柱子，弹出栈顶while (!li.empty() && nums[li.top()] >= nums[i]){li.pop();}// 2.若栈为空，说明左侧无更矮柱子，ans[i] = 0// 否则 ans[i] = 栈顶柱子下标，即左侧第一个更矮柱子位置ans[i] = li.empty() ? 0 : li.top();// 3.当前柱子下标入栈，供后续柱子判断li.push(i);}// 返回所有柱子左侧第一个更矮柱子的位置数组return ans;  
}// 函数 rii 用于计算每个柱子右侧第一个高度小于它的柱子位置（单调栈实现）
vector<int> rii(const vector<int>& nums, int n)
{// 单调栈，存放柱子下标，栈内保持对应高度递增（严格递增）stack<int> ri; // ans[i] 表示第 i 根柱子右侧第一个比它矮的柱子位置，若无则为 n+1              vector<int> ans(n + 1, 0);  // 从右到左遍历每根柱子for (int i = n; i >= 1; i--){// 1.当栈顶柱子高度 >= 当前柱子高度，说明栈顶柱子无法成为右侧第一个更矮柱子，弹出栈顶while (!ri.empty() && nums[ri.top()] >= nums[i]){ri.pop();}// 2.若栈为空，说明右侧无更矮柱子，ans[i] = n + 1（超出范围）// 否则 ans[i] = 栈顶柱子下标，即右侧第一个更矮柱子位置ans[i] = ri.empty() ? n + 1 : ri.top();// 3.当前柱子下标入栈，供后续柱子判断ri.push(i);}// 返回所有柱子右侧第一个更矮柱子的位置数组return ans;  
}signed main()
{int n;while (true){// 读取柱子数量cin >> n;if (n == 0) break;  // 输入为 0 时结束// 记录最大矩形面积int ans = 0;  // 存储柱子高度，1-based 方便索引vector<int> hei(n + 1, 0);  // 读取每根柱子高度for (int i = 1; i <= n; i++){cin >> hei[i];}// 计算每根柱子左侧第一个比它矮的柱子位置vector<int> li = lii(hei, n);// 计算每根柱子右侧第一个比它矮的柱子位置vector<int> ri = rii(hei, n);// 遍历每根柱子，计算以该柱子为高的最大矩形面积for (int i = 1; i <= n; i++){// 当前柱子高度int height = hei[i];   // 当前柱子可扩展的最大宽度（右界-左界-1） // 注意：左界的 越界存储 “0” 与//      右界的 越界存储 “n+1” // 是以下公式的关键基础          int width = ri[i] - li[i] - 1;    // 更新最大面积   ans = max(ans, height * width);      }// 输出该组数据的最大矩形面积cout << ans << endl;}
}