- 【用途】利用stack維護單純遞增或單純遞減的資料，用來找出下一個更大(或更小)的值。
- 【時間複雜度】O(N)
- 【範例】HDU 1506 Largest Rectangle in a Histogram
- 範例依題意可以轉化為尋找每一條柱(下圖編號1～7)的左右邊界。
- 以三號柱為例：
- 左邊界：三號柱左邊第一個比它低的柱子，為二號柱。
- 右邊界：三號柱右邊第一個比它低的柱子，為五號柱。
- 從三號柱的視角，所能構成的最大矩形面積，h[3] * (R[5] – L[5] – 1) = h[3] * (5 – 2 – 1)。
- 【實作】進行兩次單調棧的運作，一次由左而右，一次由右而左。
- h[1~N]：存放讀入的測資。
- 為了方便處理，在資料的前端和後端加入 h[0] = h[N+1] = -1。
- stack中存放的是資料的index，隨時維持資料單調遞增的特性。
- 當新進資料(如圖5中的 i = 5)比stk.front()對應的值小時，開始把stack中比新進值大的都pop出來(如圖5中的index-3/4)。這些index的右界即為 5。
- 兩次單調棧的運作之間，記得清空stack。
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
#define ll long long
const int maxn = 100005;
int N;
ll h[maxn];
ll L[maxn], R[maxn];
int main() {
while (cin >> N) {
if (N == 0) break;
for (int i=1; i<=N; i++) {
cin >> h[i];
}
h[0] = -1;
h[N+1] = -1;
stack<int> stk;
for (int i=1; i<=N+1; i++) {
while (stk.size() && h[stk.top()] > h[i]){
int cur = stk.top();
stk.pop();
R[cur] = i;
}
stk.push(i);
}
while (stk.size()) stk.pop();
for (int i=N; i>=0; i--) {
while (stk.size() && h[stk.top()] > h[i]){
int cur = stk.top();
stk.pop();
L[cur] = i;
}
stk.push(i);
}
ll mx = 0;
for (int i=1; i<=N; i++){
mx = max(mx, h[i] * (R[i] - L[i] - 1));
}
cout << mx << '\n';
}
return 0;
}
Post Views (since April 2021) : 3,013