【筆記】Monotonic Stack 單調棧

  • 【用途】利用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;
}
分享本文 Share with friends