POJ2559
題意：給你一個柱狀圖眷射，讓你找出圖中能組成的矩形面積最大為多少∮客ィ可轉(zhuǎn)化為對于一個序列，對于任意區(qū)間都有一個貢獻(xiàn)坐榆，區(qū)間最小值乘于區(qū)間的長度為該區(qū)間的貢獻(xiàn)，求這個序列貢獻(xiàn)最大值為多少席镀。
思路：

對序列中每個元素 i 夏漱，以它為最小值向兩邊擴(kuò)展，當(dāng)前的貢獻(xiàn)值為擴(kuò)展長度 len 乘 元素值 val, 求出最大的貢獻(xiàn)值挂绰。
如果要一直擴(kuò)展下去，必須當(dāng)前元素值不小于擴(kuò)展元素值交播。
如果我們從第 1 個元素計算到第 n 個元素，計算到元素 i 時秦士，
如果我們能快速的找出左邊第一個比 i 小的元素永高，就可以完成向左的擴(kuò)展提针，
而右擴(kuò)展次洼，這個過程本來就是一直在向右走，所以直接擴(kuò)展即可卖毁。
用單調(diào)遞減棧來維護(hù)這個過程落萎，棧內(nèi)儲存的為坐標(biāo)i。
在每個元素入棧的時候练链，更新入棧元素向左擴(kuò)展的最小位置
在每個元素出棧的時候，更新棧內(nèi)元素向右擴(kuò)展的最大位置

AC代碼:

#include <cstdio>
#include <iostream>
#include <stack>
#include <string.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> iip;
typedef pair<ll, ll> llp;
const int MAXN = 200005;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;

int i, j, n, a[MAXN], l[MAXN], r[MAXN], top;
ll ans;
stack<int> s;

int main()
{
    while(scanf("%d", &n) != EOF && n) {
        for(i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        ans = 0;
        for(i = 0; i < n; i++) {
            while(!s.empty() && a[i] < a[s.top()]) {
                r[s.top()] = i;
                s.pop();
            }
            if(s.empty())   l[i] = 0;
            else if(a[i] == a[s.top()])  l[i] = l[s.top()];
            else  l[i] = s.top() + 1;
            s.push(i);
        }
        while(!s.empty()) {
            r[s.top()] = i;
            s.pop();
        }
        for(i = 0; i < n; i++) {
            ans = max(ans, 1ll * a[i] * (r[i]-l[i]));
        }
        printf("%lld\n", ans);
//        cout.flush();
    }
    return 0;
}

POJ3494
題意：給你一個n*m的矩陣届吁，矩陣的每個位置值為0或者1绿鸣，問你在這個矩陣中全部由1組成的最大的矩形面積為多少疚沐。
思路：矩陣中的子矩陣等同于序列中的子序列潮模，只不過此題要做一個預(yù)處理，將這個矩陣分為以每一行為x軸的n個柱狀圖擎厢，對于每一個等于1的點，它的高度都等于上一行同一列的點的高度加一芬探。初始化后厘惦，再對n個柱狀圖進(jìn)行如上題POJ2559的處理偷仿。
例如：

例子

初始化后

以第一行為 x 軸

以第二行為 x 軸

以第三行為 x 軸

AC代碼：

#include<cstdio>
#include<stack>
#include<string.h>
#include <iostream>
using namespace std;

typedef long long ll;
typedef pair<int, int> iip;
typedef pair<ll, ll> llp;
const int MAXN = 2005;
int i, j, n, m, a[MAXN][MAXN] = {0}, cnt[MAXN][MAXN] = {0}, ans = 0, l[MAXN], r[MAXN];
stack<int> s;

void init() {
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            if(a[i][j] == 1) {
                cnt[i][j] = cnt[i-1][j] + 1;
            }
        }
    }
}

int main() {
    while(scanf("%d%d", &n, &m) != EOF) {
        memset(cnt, 0, sizeof(cnt));
        for(i = 1; i <= n; i++) {
            for(j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);
                if(a[i][j] == 1) {
                    cnt[i][j] = 1;
                }
            }
        }
        init();
        ans = 0;
        for(i = 1; i <= n; i++) {
            int tmp = 1;
            for(j = 1; j <= m; j++) {
                if(cnt[i][j] == 0) {
                    while(!s.empty()) {
                        r[s.top()] = j;
                        s.pop();
                    }
                    tmp = j+1;
                } else {
                    while(!s.empty() && cnt[i][j] < cnt[i][s.top()]) {
                        r[s.top()] = j;
                        s.pop();
                    }
                    if(s.empty())   l[j] = tmp;
                    else if(cnt[i][j] == cnt[i][s.top()])   l[j] = l[s.top()];
                    else l[j] = s.top() + 1;
                    s.push(j);
                }
            }
            while(!s.empty()) {
                r[s.top()] = j;
                s.pop();
            }
            for(j = 1; j <= m; j++) {
                ans = max(ans, cnt[i][j] * (r[j] - l[j]));
            }
         }
        printf("%d\n", ans);
//        cout.flush();
    }
    return 0;
}