【单调栈】-----【小A的柱状图】

小A的柱状图

题目链接

题目描述

柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形，但是小A的柱状图却不是一个规范的柱状图，它的每个矩形下端的宽度可以是不相同的一些整数，分别为$a[i]$，每个矩形的高度是$h[i]$，现在小A只想知道，在这个图形里面包含的最大矩形面积是多少。

输入描述

• 一行一个整数 $N$，表示长方形的个数
• 接下来一行 $N$ 个整数表示每个长方形的宽度
• 接下来一行 $N$ 个整数表示每个长方形的高度

输出描述

一行一个整数，表示最大的矩形面积

示例 1

输入

7
1 1 1 1 1 1 1
2 1 4 5 1 3 3

输出

8

说明

样例如图所示，包含的最大矩形面积是 8。

数据范围

• $1\le n\le 10^6$
• $1\le a[i]\le 100$
• $1\le h[i]\le 10^9$

题解（单调栈 + 前缀和）

单调栈原理见本文
前置题目见本文

一、问题抽象

我们的问题可以等价于：

给定若干个高度不等、宽度也不等的矩形，从中选择一个连续的子区间，使得该区间中所有矩形的高度都不小于某个 $h$，从而形成面积最大的矩形区域。

与经典的柱状图最大矩形问题不同点在于：

• 每个柱子的宽度不再是固定值 $1$，而是任意正整数 $a[i]$；
• 所以我们不能用下标差 $r-l-1$ 来计算宽度，而必须使用前缀和数组进行区间宽度的快速求解。

二、解法思路

Step 1：计算每个柱子的左边界 $L_i$

对于每根柱子 $i$，我们希望找到其左边第一个比它矮的柱子的位置，记为 $L_i$。

这可以使用单调递增栈完成，栈中存放的是柱子下标，确保栈顶元素对应的柱子高度严格递增。

Step 2：计算每个柱子的右边界 $R_i$

同理，从右往左遍历，找出每根柱子右侧第一个比它矮的柱子位置 $R_i$。

此时也用单调递增栈，方向相反，栈中依然维护下标，快速剔除不可能作为边界的柱子。

注意：如果某一侧没有更矮柱子，则左边界设为 $0$，右边界设为 $n+1$，表示整个图形的边界。

Step 3：使用前缀和计算宽度

由于每根柱子的宽度不同，我们构造一个前缀和数组 sum[i]：

• 表示前 $i$ 个矩形的总宽度；
• 可以用来快速求任意区间 $[l+1,r-1]$ 中的总宽度。

所以，以第 $i$ 根柱子为高、左右能扩展到 $[L_i+1,R_i-1]$，总宽度为：

$\text{宽度}$= $\text{sum}[R_i-1]$ - $\text{sum}[L_i]$

Step 4：计算所有矩形面积，取最大值

以每根柱子为“最矮柱子”计算可扩展的矩形面积：

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

最终在所有柱子中取最大面积即可。

三、完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

// 函数 lmin：求每个位置左侧第一个比它矮的位置（单调递增栈）
vector<int> lmin(const vector<int>& nums, int n)
{
    // 定义单调栈，栈中存放的是下标，保持栈内高度递增
    stack<int> value;

    // ender[i] 表示 i 左边第一个比 nums[i] 小的位置（下标）
    // 若无更矮柱子，则设置为 0
    vector<int> ender(n + 1, 0);

    // 从左到右扫描每个位置
    for (int i = 1; i <= n; i++)
    {
        // 1.弹出栈顶元素，直到遇到比当前高度小的位置为止
        while (!value.empty() && nums[value.top()] >= nums[i])
        {
            value.pop();
        }

        // 2.若栈为空，说明左侧无更矮柱子，设置为 0
        // 否则栈顶即为左边第一个比当前柱子矮的位置
        ender[i] = value.empty() ? 0 : value.top();

        // 3.当前柱子入栈
        value.push(i);
    }

    // 返回左边界数组
    return ender;
}

// 函数 rmin：求每个位置右侧第一个比它矮的位置（单调递增栈）
vector<int> rmin(const vector<int>& nums, int n)
{
    // 定义单调栈，栈中存放的是下标，保持栈内高度递增
    stack<int> value;

    // ender[i] 表示 i 右边第一个比 nums[i] 小的位置（下标）
    // 若无更矮柱子，则设置为 n+1（越界值）
    vector<int> ender(n + 1, 0);

    // 从右到左扫描每个位置
    for (int i = n; i >= 1; i--)
    {
        // 1.弹出栈顶元素，直到遇到比当前高度小的位置为止
        while (!value.empty() && nums[value.top()] >= nums[i])
        {
            value.pop();
        }

        // 2.若栈为空，说明右侧无更矮柱子，设置为 n+1
        // 否则栈顶即为右边第一个比当前柱子矮的位置
        ender[i] = value.empty() ? n + 1 : value.top();

        // 3.当前柱子入栈
        value.push(i);
    }

    // 返回右边界数组
    return ender;
}

signed main()
{
    // 读取矩形数量
    int n;
    cin >> n;

    // wei[i] 表示第 i 个矩形的宽度
    // hei[i] 表示第 i 个矩形的高度
    vector<int> wei(n + 1);
    vector<int> hei(n + 1);

    // 读取每个矩形的宽度（下标从 1 开始）
    for (int i = 1; i <= n; i++)
    {
        cin >> wei[i];
    }

    // 读取每个矩形的高度
    for (int i = 1; i <= n; i++)
    {
        cin >> hei[i];
    }
	
	// 使用前缀和来快速求出任意区间的总宽度
    // sum[i] 表示前 i 个矩形的总宽度，用于快速计算任意区间宽度
    vector<int> sum(n + 1, 0);

    // 初始化前缀和
    sum[1] = wei[1];

    // 构造前缀和数组
    for (int i = 2; i <= n; i++)
    {
        sum[i] = sum[i - 1] + wei[i];
    }

    // 计算每个位置左侧第一个比它矮的柱子下标
    vector<int> ender1 = lmin(hei, n);

    // 计算每个位置右侧第一个比它矮的柱子下标
    vector<int> ender2 = rmin(hei, n);

    // 记录最大矩形面积
    int ans = 0;

    // 遍历每个柱子，考虑以它为高的最大矩形
    for (int i = 1; i <= n; ++i)
    {
        // 左边界（不包含）
        int l = ender1[i];

        // 右边界（不包含）
        int r = ender2[i];

        // 当前柱子可扩展的矩形区域是区间 [l + 1, r - 1]
        // 宽度为 sum[r - 1] - sum[l]
        int width = sum[r - 1] - sum[l];

        // 面积 = 高度 × 宽度
        int area = hei[i] * width;

        // 更新最大面积
        ans = max(ans, area);
    }

    // 输出结果
    cout << ans << endl;

    return 0;
}

四、时间复杂度分析

• 单调栈找左右边界时间复杂度为 $O(n)$；
• 构造前缀和数组复杂度 $O(n)$；
• 遍历计算所有面积复杂度 $O(n)$；

所以整体时间复杂度为：

$O(n)$

空间复杂度同样是 $O(n)$，用于存储前缀和与边界数组。

五、总结

本题是「最大矩形面积」问题的变种，处理了宽度不等的情况。

解题核心：

1. 单调栈快速寻找左右边界，避免暴力；
2. 用前缀和代替下标差求区间宽度；
3. 每根柱子作为“最矮的”核心，计算能扩展的最大矩形。