单调栈-POJ2559，POJ3494

POJ2559
题意：给你一个柱状图，让你找出图中能组成的矩形面积最大为多少。可转化为对于一个序列，对于任意区间都有一个贡献，区间最小值乘于区间的长度为该区间的贡献，求这个序列贡献最大值为多少。
思路：

对序列中每个元素 i ，以它为最小值向两边扩展，当前的贡献值为扩展长度 len 乘元素值 val, 求出最大的贡献值。
如果要一直扩展下去，必须当前元素值不小于扩展元素值。
如果我们从第 1 个元素计算到第 n 个元素，计算到元素 i 时，
如果我们能快速的找出左边第一个比 i 小的元素，就可以完成向左的扩展，
而右扩展，这个过程本来就是一直在向右走，所以直接扩展即可。
用单调递减栈来维护这个过程，栈内储存的为坐标i。
在每个元素入栈的时候，更新入栈元素向左扩展的最小位置
在每个元素出栈的时候，更新栈内元素向右扩展的最大位置

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组成的最大的矩形面积为多少。
思路：矩阵中的子矩阵等同于序列中的子序列，只不过此题要做一个预处理，将这个矩阵分为以每一行为x轴的n个柱状图，对于每一个等于1的点，它的高度都等于上一行同一列的点的高度加一。初始化后，再对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;
}

最后编辑于：2019.04.28 19:05:55