小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] 小的位置（下标）// 若无更矮柱子，则设置为 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;
}

---

四、时间复杂度分析

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

所以整体时间复杂度为：

$O(n)$

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

---

五、总结

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

解题核心：

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

---