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

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

news 2025/6/23 7:06:49

小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。

数据范围

$\leq n \leq 10^6$
$\leq a[i] \leq 100$
$\leq h[i] \leq 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] 小的位置（下标）// 若无更矮柱子，则设置为 0vector<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;
}