直方圖中最大的矩形（單調棧）

題目

題 目 傳 送 門 題目傳送門 題目傳送門

題解

• 如果矩形的高度從左向右單調遞增，那麼我們可以枚舉每個矩形的高度，并把寬度延伸到左右邊界，來計算面積，從中取得最大值來得到答案。
• 但實際上矩形高度不可能是單調遞增的。
• 那麼我們可以維護一個高度遞增且寬度遞增的矩形序列。

• 具體過程：

  我們可以建一個棧用來儲存每個矩形的高度。

  從左向右周遊每個矩形，如果高度比棧頂高直接進棧。

  如果高度小于棧頂，則不斷取出棧頂，直到棧頂高度比目前高度小，在出棧的過程中我們累加出棧矩形的寬度，每彈出一個矩形就用高度乘以寬度來記錄該矩形的面積，在整個過程結束後我們把一個寬度為目前累加的寬度，高度為目前寬度的矩形進棧。

code

#include <bits/stdc++.h> 
using namespace std; 
const int maxn = 1e5 + 1000; 
typedef long long LL; 

template <typename T> 
inline void read(T &s) {
    s = 0; 
    T w = 1, ch = getchar(); 
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
    s *= w; 
}

int n, cnt; 
LL ans; 
LL a[maxn], s[maxn], w[maxn]; 

int main() {
	while (scanf("%d", &n) && n != 0) { 
		a[n + 1] = 0; 
		cnt = 0; 
		ans = 0; 
		memset(s, 0, sizeof(s)); 
		memset(w, 0, sizeof(w)); 
		
		for (int i = 1; i <= n; ++i) read(a[i]); 
		for (int i = 1; i <= n + 1; ++i) {
			if (a[i] > s[cnt]) {
				s[++cnt] = a[i]; 
				w[cnt] = 1; 
			} else {
				int width = 0; 
				while (s[cnt] > a[i]) {
					width += w[cnt]; 
					ans = max(ans, (LL) width * s[cnt]); 
					cnt--; 
				}
				s[++cnt] = a[i]; 
				w[cnt] = width + 1; 
			}
		}
		printf("%lld\n", ans); 
	}
	return 0; 
}