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

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)$

这在 $n\le 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;
    }
}

六、时间复杂度分析

• 每根柱子入栈、出栈至多一次；
• 求左右边界时间复杂度均为 $O(n)$；
• 最终遍历一次数组计算面积也是 $O(n)$

因此总时间复杂度为：

$O(n)$

空间复杂度为 $O(n)$，用于存储栈和左右边界数组。

七、总结

• 本题是单调栈最典型的应用之一，掌握这个模板对很多区间最大/最小、滑动窗口问题都有极大帮助。
• 单调栈的核心思想是：用栈保存候选边界元素，用单调性剔除不可能的选择，从而压缩搜索空间。
• 注意左边界用 0、右边界用 n+1 的越界设定，是公式统一性的重要保障。