欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

单调栈简单题目整理

程序员文章站 2022-03-20 18:51:21
最大矩阵类问题1.求最大矩阵题目链接题目:直方图中的最大矩阵#include#define pb push_back#define fi first#define se second#define ALL(a) a.begin(), a.end()#define SZ(a) (int)a.size()#define db1(x) cout<<#x<<" = "<

最大矩阵类问题

1.求最大矩阵

题目链接

题目:直方图中的最大矩阵

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)a.size()
#define db1(x) cout<<#x<<" = "<<x<<endl
#define db2(x, y) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
#define endl "\n"
//#define int long long
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6+10;
int n;
ll h[N];
int w[N], p[N];
void sol() {
    for(int i = 1;i <= n; ++i) scanf("%lld", &h[i]);
    h[n+1] = 0;
    int c = 0;
    ll ma = 0;
    for(int i = 1;i <= n+1; ++i) {
        ll x = h[i];
        if(h[i]>=p[c]) {
            p[++c] = h[i];
            w[c] = 1;
        }
        else {
            int width = 0;
            while(h[i]<p[c]) {
                width += w[c];
                ma = max(ma, 1ll*width*p[c--]);
            }
            p[++c] = h[i]; w[c] = width+1;
        }
    }
    printf("%lld\n", ma);
}
int main()
{
    while(scanf("%d", &n), n)
    sol();
    return 0;
}
2 求最大正方形,也就是最大矩阵稍微改改

题目链接

题目:城市游戏

需要先预处理从当前位置向右边连续的F的个数O(n^2)
然后枚举起始列,对每一列进行一个单调栈处理出最大正方形O(n^2)

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)a.size()
#define db1(x) cout<<#x<<" = "<<x<<endl
#define db2(x, y) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
#define endl "\n"
#define inf 0x3f3f3f3f
#define MEM(a, b) memset(a, b, sizeof(a))
//#define int long long
using namespace std;
typedef long long ll;
typedef pair<string, int> pii;
typedef pair<int, int> piii;
typedef unsigned long long ull;
const int N = 2010, maxn = 1e6+10;
const ll mod = 1e9+7;

int n, m, k;
char s[N][N];
int num[N][N];

int calc(int x)
{
    int h[N], w[N], p[N], c = 0;
    for(int i = 1; i <= n; ++i) h[i] = num[i][x], w[i] = p[i] = 0;
    h[0] = 0;
    h[n+1] = 0;
    p[0] = 0;

    int ans = 0;
    for(int i = 1;i <= n+1; ++i) {
        if(h[i] >= p[c]) p[++c] = h[i], w[c] = 1;
        else {
            int width = 0;
            while(h[i] < p[c]) {
                width += w[c];
                ans = max(ans, width*p[c--]);
            }
            p[++c] = h[i], w[c] = width+1;
        }
    }
    return ans;
}
void sol() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= m; ++j) scanf(" %c", &s[i][j]);

    for(int i = 1;i <= n; ++i)
    for(int j = 1;j <= m; ++j)
    {
        if(s[i][j] == 'F') num[i][j] = 1;
        else continue;
        if(num[i][j-1]>1&&s[i][j]==s[i][j-1]) {
            num[i][j] = num[i][j-1]-1;
        }
        else {
            int k = j;
            while(k+1 <= m&&s[i][j]==s[i][k+1]) k++, num[i][j]++;
        }
    }
    int ans = 0;
    for(int st = 1; st <= m; ++st)
    ans = max(ans, calc(st));
    printf("%lld\n", 3ll*ans);
}
signed main()
{
    sol();
}

最近的最高或最低的位置问题。

1 模板类

题目链接

题目:仰视奶牛

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)a.size()
#define db1(x) cout<<#x<<" = "<<x<<endl
#define db2(x, y) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
#define endl "\n"
#define inf 0x3f3f3f3f
#define MEM(a, b) memset(a, b, sizeof(a))
//#define int long long
using namespace std;
typedef long long ll;
typedef pair<string, int> pii;
typedef pair<int, int> piii;
typedef unsigned long long ull;
const int N = 2e5+10, maxn = 1e6+10;
const ll mod = 1e9+7;
int n, m, k;
int h[N], p[N], ans[N];
void sol() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &h[i]);
    int c = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(c==0||h[i]<=h[p[c]]) p[++c] = i;
        else {
            while(c!=0&&h[i]>h[p[c]]) {
                ans[p[c--]] = i;
            }
            p[++c] = i;
        }
    }
    for(int i = 1;i <= n; ++i)
    printf("%d\n", ans[i]);
}
signed main()
{
    sol();
}
2 接雨水类

题目链接

题目:接雨水

维护一个单调严格递减的栈,若当前柱子高于栈顶的柱子,退栈直到符合单调性;否则加入栈顶。每次退栈时,累加雨水的体积(每次算一层)

#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)a.size()
#define db1(x) cout<<#x<<" = "<<x<<endl
#define db2(x, y) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
#define endl "\n"
#define inf 0x3f3f3f3f
#define MEM(a, b) memset(a, b, sizeof(a))
//#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef unsigned long long ull;
const int N = 2e5+10, maxn = 1e6+10;
const ll mod = 1e9+7;

int n, m, k;
int h[N];
void sol() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &h[i]);
    stack<int> st;
    ll ans = 0;
    for(int i = 1;i <= n; ++i)
    {
        while(!st.empty()&&h[st.top()]<h[i]) {
            int t = st.top(); st.pop();
            if(!st.empty()){
                int l = i-st.top()-1;
                int w = min(h[i], h[st.top()])-h[t];
                ans += l*w;
            }
        }
        st.push(i);
    }
    printf("%lld\n", ans);
}
signed main()
{
    sol();
}

本文地址:https://blog.csdn.net/weixin_44070289/article/details/109255222