小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. 每根柱子作為“最矮的”核心，計算能擴展的最大矩形。

---