單調(diào)棧：進(jìn)棧元素單調(diào)遞增（減）的棧漾月，如果碰到比棧頂元素大的元素就進(jìn)棧病梢，否則不斷把棧頂元素彈出直到棧頂元素小于等于要進(jìn)棧的元素或者棧為空。
應(yīng)用：
已知一個(gè)數(shù)列梁肿，求每一個(gè)元素后面第一個(gè)比它大的元素到它的距離蜓陌，如果沒(méi)有，輸出0吩蔑。此類問(wèn)題僅和元素下標(biāo)差以及元素的值有關(guān)钮热，而且問(wèn)題具有對(duì)下標(biāo)和對(duì)值的單調(diào)性，可以用這種方法把的算法變成的算法烛芬。

#include<iostream>
#include<stack>
using namespace std;
int n;
int a[100010];
int res[100010];
typedef struct {
    int t;
    int pos;
}T;
stack<T> s;
T now, temp;
int main() {
    while (cin >> a[n++]);
    n--;
    for (int i = 0; i < n; i++) {
        now.pos = i;
        now.t = a[i];
        if (s.empty() || s.top().t > a[i]) {
            s.push(now);
        }
        else if (s.top().t == a[i]) continue;
        else {
            while (!s.empty() && s.top().t <= a[i]) {
                temp = s.top();
                s.pop();
                res[temp.pos] = i - temp.pos;
            }
            s.push(now);
        }
    }
    while (!s.empty()) {
        res[s.top().pos] = 0;
        s.pop();
    }
    for (int i = 0; i < n; i++) cout << res[i] << ' ';
    return 0;
}

例題：
最大長(zhǎng)方形：http://poj.org/problem?id=2559（原題的網(wǎng)站上不去）
先看最大正方形：https://www.luogu.org/problem/P1387
已知一個(gè)0-1矩陣a[M][N]隧期，求只包含1的最大正方形的面積。
設(shè)為以為右下角的最大正方形邊長(zhǎng)赘娄，易知第一行和第一列的0方格的值為0仆潮，1方格的dp值為1。
對(duì)于其他的方格遣臼，如果它是0方格性置，dp值為0；如果它是1方格揍堰，則考慮它的左邊鹏浅，上邊和左上邊，如果有任意一個(gè)方格為0屏歹，則它的dp值為1（只有它自己）隐砸，否則它的dp值為相鄰三個(gè)方格dp值的最小值再加1，因?yàn)樽鳛樽钚≈祄in西采，說(shuō)明它左上方的方格的左上方至少有一個(gè)min*min的正方形凰萨，它上方和左方的方格一定能向上和向左擴(kuò)展出min，再加上它自己，邊長(zhǎng)為min+1胖眷，即：

動(dòng)態(tài)規(guī)劃即可武通。

#include<iostream>
#include<algorithm>
using namespace std;
int h, w;
bool a[1405][1405];
int dp[1405][1405];
int res;
int main() {
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
            a[i][j] = !a[i][j];
        }
    }
    for (int i = 0; i < h; i++) {
        if (!a[i][0]) dp[i][0] = 1;
    }
    for (int j = 0; j < w; j++) {
        if (!a[0][j]) dp[0][j] = 1;
    }
    for (int i = 1; i < h; i++) {
        for (int j = 1; j < w; j++) {
            if (a[i][j]) dp[i][j] = 0;
            else {
                dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                res = max(res, dp[i][j]);
            }
        }
    }
    cout << res;
    return 0;
}

時(shí)間復(fù)雜度：。
最大長(zhǎng)方形：把上題的正方形改成長(zhǎng)方形珊搀。
動(dòng)態(tài)規(guī)劃不對(duì)了冶忱，因?yàn)殚L(zhǎng)方形長(zhǎng)寬不一樣囚枪。
最樸素的想法：枚舉所有點(diǎn)劳淆，找它們能構(gòu)成的最大長(zhǎng)方形面積的最大值。聯(lián)想關(guān)燈問(wèn)題括勺，可以按順序做曲掰，枚舉每一行以為底的高最短的長(zhǎng)方形面積，對(duì)于高可以用預(yù)處理算出來(lái)乱豆，即從上往下算最多能連續(xù)多少個(gè)1宛裕，顯然有趾徽，用動(dòng)態(tài)規(guī)劃容易算得，問(wèn)題轉(zhuǎn)化為求直方圖上的最大長(zhǎng)方形面積疲酌，預(yù)處理的時(shí)間復(fù)雜度為朗恳。
然后遍歷每一行载绿，每一行再遍歷每一組，去最小高乘寬度再取最大值怀浆，時(shí)間復(fù)雜度為。
下面用單調(diào)棧把復(fù)雜度降到：
棧儲(chǔ)存直方圖上長(zhǎng)方形的高和左端的位置pos镰踏。
對(duì)每一行沙合，從左往右枚舉元素：
若棧為空或者棧頂元素的高小于要入棧元素的高，就入棧绊率。
否則出棧到棧頂元素的高小于要入棧元素的高為止究履，設(shè)置pos為最后一個(gè)出棧元素的pos最仑，入棧，在這個(gè)過(guò)程中，對(duì)于每一個(gè)出棧的元素蜜葱，都計(jì)算它和已出棧元素所能形成的最大長(zhǎng)方形的面積：，直到所有元素都入過(guò)棧爸黄，把棧內(nèi)的元素清空揭鳞。
這樣實(shí)際上每一行只遍歷了一遍，時(shí)間復(fù)雜度為称开。
部分代碼（求柱狀圖的最大矩形鳖轰，能過(guò)poj2559）：

#pragma warning(disable:4996)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int n;
ll a[maxn];
ll res;
typedef struct {
    ll pos;
    ll h;
}rect;
stack<rect> s;
int main() {
    rect now, temp;
    while (1) {
        scanf("%d", &n);
        if (n == 0) break;
        for (int i = 0; i < n; i++) scanf("%I64d", &a[i]);
        res = 0;
        a[n] = -1;
        for (int i = 0; i <= n; i++) {
            now.pos = i;
            now.h = a[i];
            if (s.empty() || a[i] > s.top().h) {
                s.push(now);
            }
            else if (a[i] == s.top().h) continue;
            else {
                temp.pos = i;
                while (!s.empty() && a[i] <= s.top().h) {
                    temp = s.top();
                    s.pop();
                    res = max(res,ll((i - temp.pos)*temp.h));
                }
                now.pos = temp.pos;
                s.push(now);
            }
        }
        printf("%I64d\n", res);
    }

    return 0;
}

單調(diào)隊(duì)列：https://www.luogu.org/problem/P1886
連續(xù)移動(dòng)區(qū)間的最值問(wèn)題蕴侣。
首先想到可以用樹狀數(shù)組臭觉，時(shí)間復(fù)雜度為辱志，似乎很好揩懒，但是此題客冈，场仲，這樣還是會(huì)超時(shí)。
1s的時(shí)間限制鸽素，對(duì)應(yīng)及以上亦鳞，對(duì)應(yīng)，對(duì)應(yīng)遭笋。
用單調(diào)隊(duì)列可以把時(shí)間復(fù)雜度降到瓦呼。
如果隊(duì)列為空测暗，從隊(duì)尾進(jìn)隊(duì)；否則比較要進(jìn)隊(duì)的元素和隊(duì)尾元素质和，如果它比隊(duì)尾元素大稚字，就進(jìn)隊(duì)，否則出隊(duì)直到隊(duì)尾元素比它小褒傅，進(jìn)隊(duì)袄友。如果要進(jìn)隊(duì)的元素和隊(duì)首元素下標(biāo)差大于等于，隊(duì)首元素從隊(duì)首出隊(duì)（相當(dāng)于滑動(dòng)）支竹。
STL實(shí)現(xiàn)：

#include<iostream>
#include<deque>
using namespace std;
int n, k;
const int maxn = 1000010;
struct S {
    int pos;
    int val;
}a[maxn];
deque<S> q;
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].val;
        a[i].pos = i;
    }
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && q.back().val >= a[i].val) q.pop_back();
        q.push_back(a[i]);
        if (a[i].pos - q.front().pos >= k) q.pop_front();
        if (i >= k) cout << q.front().val << ' ';
    }
    cout << endl;
    q.clear();
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && q.back().val <= a[i].val) q.pop_back();
        q.push_back(a[i]);
        if (a[i].pos - q.front().pos >= k) q.pop_front();
        if (i >= k) cout << q.front().val << ' ';
    }
    return 0;
}

數(shù)組實(shí)現(xiàn)：一定要記住設(shè)tail=0,head=1,判斷非空的條件是head<=tail礼搁，不這樣的話會(huì)出現(xiàn)++tail首元素沒(méi)讀，tail++從隊(duì)首出隊(duì)錯(cuò)誤扎运。

#include<iostream>
using namespace std;
const int maxn = 1000010;
int n, k;
struct S {
    int pos;
    int val;
}a[maxn], q[maxn];
int head, tail;
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].val;
        a[i].pos = i;
    }
    head = 1;
    for (int i = 1; i <= n; i++) {
        while (head <= tail && q[tail].val >= a[i].val) tail--;
        q[++tail] = a[i];//注意是++tail饮戳，不是tail++
        if (a[i].pos - q[head].pos >= k) head++;
        if (i >= k) cout << q[head].val << ' ';
    }
    cout << endl;
    head = 1;
    tail = 0;
    for (int i = 1; i <= n; i++) {
        while (head <= tail && q[tail].val <= a[i].val) tail--;
        q[++tail] = a[i];
        if (a[i].pos - q[head].pos >= k) head++;
        if (i >= k) cout << q[head].val << ' ';
    }
    return 0;
}