単調なスタックはUSACO 06 NOV、Larget Rectanglen a Higogr、POJ 2796を整理します.

単調なスタック
スタック
一つのデータ構造は、端だけに挿入と削除操作を行うことができる特殊な線形表であり、それは先進的な後に出る原則に従ってデータを先に格納するデータはスタックの底に押し込まれ、最後のデータはスタックの上にある.
単調なスタック
スタック内部の要素は単調なデータ構造であり、単調なインクリメントスタックと単調な逓減スタックに分けられる.
性質

は、スタックの底からスタックの一番上までの要素を満たすための単調性

を有する.

はスタックの先進的なポスト特性を満足し、スタックの一番上に近い要素ほど早くスタック

を出ます.
実現する
単調なインクリメントスタックの場合、現在のスタックの要素はx x xである.

現在のスタックが空またはx≧x\ge x≧スタックトップ要素であれば、直接x xをスタックに入れる.

もしx＜x＜スタックトップ要素がスタックを空またはx≧x\ge x≧スタックトップ要素

を満たすまで連続的にスタックのトップ要素をスタックしているならば.
例えば、5列5、4、6、2、4、3、6、5｛5、4、6、2、4、4、3、5｝5、4、6、5｝があります.5、4、6、2、4、3、6、5は、このように1つの単調なインクリメントスタックを構成して、各数の実現過程について

は

に入る.

は倉庫から出て、4は倉庫に入る

.

6スタック

、6は倉庫を出して、2は倉庫に入る

4スタック

4は倉庫を出して、3は倉庫に入ります

6スタック

はスタックから出て、5は

に入ります.
コード

void push(int now) {
	stack<int> s;
	while (!s.empty() && s.top() >= now)s.pop();
	s.push(now);
}

int s[1010], top = 0;
while (top > 0 && s[top] >= now)top--;
s[++top] = now;

作用
nの長さの配列aがあり、1<=i==n 1<=i==n 1==nに対して、L(i)＝m a x(j:j＜i,a j＜a i)L(i)＝max(j:j＜i,a_｛i｝L(i)＝max(i)＝max(j:j＜i)＞i
各要素の左にある最初の元素の位置を見つけます.

は、他のスタックによって要素の位置を記録し、単調なスタックに同期したスタックインスタック動作を行う.

は、単調なスタックの要素として構造体を使用し、値と位置を同時に記録する.

は、要素の位置を単調なスタックの要素として比較するとき、位置によって要素のサイズを照会する.

[USACO 06 NOV]悪い一日のBad Hair Day
題意
農夫のジョンはN(N≦800 N\leq 80000 N≦80000)N頭の乳牛が髪の毛の日を過ごしています.どの牛も同じ列で東に向かっています.そして牛の身長はh＿i＿h＿uです.{i}hi番目のN番目の牛は一番前にいますが、1番目の牛は一番後ろでi番目の牛に対してi iから一番目の身長を超えた牛は全部彼に見られます.C[i]C[i]C[i]C[i]はi iに見られる牛の総数です.Σi=1 n C[i]sum_]を求めます.｛i=1｝^{n}C[i]Σi=1 n C[i]
分析
私たちは逆に見ることができます.彼の高さを超えるすべての牛は彼を見ることができます.単調で減少した単調なスタックを維持します.数を挿入した後、その数の前の数は彼に見られます.
コード

#include 
#include 
#include 
using namespace std;
#pragma warning (disable:4996)
typedef long long LL;
const int maxn = 80005;
int stack[maxn];
int main() {
	int top = 0, n, now;
	LL ans = 0;
	scanf("%d", &n);
	while (n--) {
		scanf("%d", &now);
		while (top > 0 && now >= stack[top])top--;
		ans += LL(top);
		stack[++top] = now;
	}
	printf("%lld
", ans);

}

Larget Rectanglen a Higogr
題意
水平線にはn個の幅が1の長方形があり、これらの長方形に含まれる最大のサブ矩形面積を求めます.
分析
この行列を単調なスタックで記録する前に、彼の行列長の合計よりも大きい、すなわちプレフィックス長である.
スタックを出る時、このマトリクスの後ろの方が彼より高いマトリクスの長さの合計を記録します.

			int width = 0;
			while (top > 0 && stack[top].first >= now) {
				width += stack[top].second;
				ans = max(ans, stack[top].first * width);
				top--;
			}
			stack[++top] = pll(now, width + 1);

コード

#include 
#include 
#include 
using namespace std;
#pragma warning (disable:4996)
typedef long long LL;
typedef pair<LL, LL> pll;
const int maxn = 100005;
pll stack[maxn];
LL a[maxn];
int main() {
	int top, n;
	while (~scanf("%d", &n) && n) {
		for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
		a[n + 1] = 0;
		top = 0;
		LL ans = 0, now, width;
		for (int i = 1; i <= n + 1; i++) {
			now = a[i]; width = 0;
			while (top > 0 && stack[top].first >= now) {
				width += stack[top].second;
				ans = max(ans, stack[top].first * width);
				top--;
			}
			stack[++top] = pll(now, width + 1);
		}
		printf("%lld
", ans);
	}
}

POJ 2796 Feel Good
題意
この区間と乗合区間の最小値が最大になるように、行列を与えます.
分析
各点の最小値を列挙する区間と区間との積(区間とプレフィックスと計算)
区間の左と右の区間は単調なスタックで彼と一番近いのは彼より小さいのが境界です.
コード

#include 
#include 
#include 
#include 
using namespace std;
#pragma warning (disable:4996)
typedef long long LL;
typedef pair<LL, LL> pii;
const LL maxn = 100005;
LL Stack[maxn], a[maxn];
LL sum[maxn];
pii l[maxn];
int main() {
	LL n, top, now, Case = 0;
	while (~scanf("%lld", &n)) {
		//memset(sum, 0, sizeof(sum));
		sum[0] = 0;
		for (LL i = 1; i <= n; i++) {
			scanf("%lld", &a[i]);
			sum[i] = sum[i - 1] + a[i];
		}
		top = 0; Stack[0] = 0;
		for (LL i = 1; i <= n; i++) {
			now = a[i];
			while (top > 0 && a[Stack[top]] >= now)top--;
			l[i].first = Stack[top] + 1;
			Stack[++top] = i;
		}
		top = 0; Stack[0] = n + 1;
		for (LL i = n; i >= 1; i--) {
			now = a[i];
			while (top > 0 && a[Stack[top]] >= now)top--;
			l[i].second = Stack[top] - 1;
			Stack[++top] = i;
		}
		LL ans = -1, g = 0;
		for (LL i = 1; i <= n; i++) {
			if ((sum[l[i].second] - sum[l[i].first - 1]) * a[i] > ans) {
				ans = (sum[l[i].second] - sum[l[i].first - 1]) * a[i];
				g = i;
			}
		}
		if (Case++)printf("
");
		printf("%lld
", ans);
		printf("%lld %lld
", l[g].first, l[g].second);
	}
}