首页 > 其他 > 详细

一类需要用到单调队列的题目

时间:2019-09-07 09:52:11      阅读:103      评论:0      收藏:0      [点我收藏+]

直方图的最大矩形面积

poj 2559
高度保持单调增,弹出时向最右看。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int n;
int h[maxn];
struct Node{
    int idx, h;
};
stack<Node> s;

int main(){
    ios::sync_with_stdio(false);
    while(~scanf("%d", &n)&&n){
        ll ans = 0;
        for(int i=0; i<n; i++) scanf("%d", &h[i]);
        h[n] = 0;
        for(int i=0; i<=n; i++){
            if(s.empty()) s.push(Node{i, h[i]});
            else if(h[i]>s.top().h){
                s.push(Node{i, h[i]});
            }
            else if(h[i]<s.top().h){
                int target = i;
                while(!s.empty()&&h[i]<=s.top().h){
                    ans = max(ans, 1ll*(i-s.top().idx)*s.top().h);
                    target = s.top().idx;
                    s.pop();
                }
                s.push(Node{target, h[i]});
            }
        }
        printf("%lld\n", ans);
    }

    return 0;
}


n*m矩阵空地周长

水坑的最大储水量

一维

  1. 给h:扫两遍
  2. 给地面的高和天花板的高:扫两遍
  3. 地面是一个三角形的斜坡:用栈

二维

  1. 仅给地面的高
    NYOJ 547
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
typedef long long ll;
ll a[310][310];
bool vis[310][310];
int n, m;
int dir[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 };
struct node{
    int x, y, v;
    bool operator < (const node & oth)const
    {
        return v > oth.v;   // 每一层都按从小到大的值排
    }
};
priority_queue<node>pq;
void bfs()
{
    ll ans = 0;
    while (!pq.empty())
    {
        int x = pq.top().x, y = pq.top().y, v = pq.top().v;
        pq.pop();
        if (vis[x][y])
            continue;
        vis[x][y] = 1;
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dir[i][0];
            int yy = y + dir[i][1];
            int vv = a[xx][yy];
            if (xx < n && xx > 1 && yy < m && yy > 1 && !vis[xx][yy])
            {
                if (vv < v) //若该点小于当前点,则可升高
                {
                    ans += v - vv;
                    a[xx][yy] = v; //更新信息
                }
                pq.push({ xx, yy, a[xx][yy] });
            }       
        }
    }
    cout << ans << endl;
}
int main(){
    while (cin >> m >> n)
    {
        memset(vis, 0, sizeof vis);
        while (!pq.empty())
            pq.pop();
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                cin >> a[i][j];
                if (i == 1 || j == 1 || i == n || j == m)
                    pq.push({ i, j, a[i][j] }); //先压入边界的点
            }
        bfs();
        /*for (int i = 1; i <= n; i++, cout << endl)
            for (int j = 1; j <= m; j++)
                cout << a[i][j] << " ";*/
    }
    return 0;
}

一类需要用到单调队列的题目

原文:https://www.cnblogs.com/babydragon/p/11478812.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!