单调栈

本文最后更新于 2024年9月18日凌晨

单调栈

原理

作用：从N个数中取出若干个数，组成单调栈（在栈中的元素是单调的）并且遵循其原来的排列顺序。（一定会选取最后一个加入的数）

假设有如下数组：

最左侧单调栈如下：

为了更好地说明单调栈的原理，引入（题目P5788 【模板】单调栈 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）。

分析：对于每一个数据都会有一个单调栈，而单调栈中上一个元素的下标就是在这个元素之后的比这个元素大的最近的元素下标。

代码如下：

#include <stdio.h>    
#define N 3000006  
int n,top;  
int a[N],r[N],sta[N];//栈的初始化为0  
int main() {  
    scanf("%d",&n);  
    for(int i=1;i<=n;i++){  
        scanf("%d",&a[i]);  
    }    double start,finish;   
    for(int i=n;i;--i){// 从后往前  
        // 退栈直到找到“a[i]<a[sta[top]]”
        //在栈中查找右边第一个比a[i]大的数  
        while(top>0&&a[sta[top]]<=a[i])--top;
        r[i]=sta[top];// 记录栈  
        sta[++top]=i;// 进栈  
    }  
    for(int i=1;i<=n;++i)printf("%d ",r[i]);    
    return 0;  
}

应用

题目1：B3666 求数列所有后缀最大值的位置 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

给定一个数列，初始为空。有次操作，每次在的末尾添加一个正整数。

每次操作结束后，请你找到当前所有的后缀最大值的下标（下标从 1 开始）。一个下标是当前的后缀最大值下标当且仅当：对于所有的，都有，其中表示当前的元素个数。

为了避免输出过大，请你每次操作结束后都输出一个整数，表示当前数列所有后缀最大值的下标的按位异或和。

输入格式

第一行是一个整数，表示操作次数。
第二行有个整数，依次表示次操作所添加的整数。

输出格式

每次操作后请输出一行一个整数，表示当前数列所有后缀最大值下标的按位异或和。

样例 #1

样例输入 #1

1 2	`5 2 1 3 5 4`

样例输出 #1

数据规模与约定

对于全部的测试点，保证，。

解析

给出样例的解析：

只有第一个数，数列为时，满足条件的下标为1，故输出1。

加入第二个数，数列为时，满足条件的下标为1，2，故输出1^2=3。

加入第三个数，数列为时，满足条件的下标为3，故输出3。

加入第四个数，数列为，满足条件的下标为4，故输出4。

加入第四个数，数列为，满足条件的下标为4,5，故输出4^5=1。

代码如下：

#include<stdio.h>  
#include<stdlib.h>  
int stm[10000007];  
int result = 0;  
int main()  
{  
    int n,top=1;  
    scanf("%d",&n);  
    unsigned long long int *p;  
    p=malloc(sizeof(long long int)*(n+1));  
    p[0]=0;//初始化  
    for(int i=1;i<=n;i++) {  
        scanf("%llu", &p[i]);  
        while (top > 0 && p[i] > p[stm[top]]) {  
            result^=stm[top];  
            top--;  //退栈
        }  
        stm[++top] = i;  
        result^=stm[top];  
        if(i!=n)printf("%d\n", result);  
        else printf("%d",result);  
    }  
    return 0;  
}

题目2：[USACO09MAR]Look Up S

题目描述

Farmer John's N (1 <= N <= 100,000) cows, conveniently numbered 1..N, are once again standing in a row. Cow i has height H_i (1 <= H_i <= 1,000,000).

Each cow is looking to her left toward those with higher index numbers. We say that cow i 'looks up' to cow j if i < j and H_i < H_j. For each cow i, FJ would like to know the index of the first cow in line looked up to by cow i.

Note: about 50% of the test data will have N <= 1,000.

约翰的头奶牛站成一排，奶牛的身高是。现在，每只奶牛都在向右看齐。对于奶牛，如果奶牛满足且，我们可以说奶牛可以仰望奶牛。求出每只奶牛离她最近的仰望对象。

Input

输入格式

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains the single integer: H_i

第行输入，之后每行输入一个身高。

出格式

* Lines 1..N: Line i contains a single integer representing the smallest index of a cow up to which cow i looks. If no such cow exists, print 0.

共行，按顺序每行输出一只奶牛的最近仰望对象，如果没有仰望对象，输出。

样例 #1

样例输入 #1

样例输出 #1

提示

FJ has six cows of heights 3, 2, 6, 1, 1, and 2.

Cows 1 and 2 both look up to cow 3; cows 4 and 5 both look up to cow 6; and cows 3 and 6 do not look up to any cow.

【输入说明】头奶牛的身高分别为 3,2,6,1,1,2。

【输出说明】奶牛 #1,#2 仰望奶牛#3，奶牛 #4,#5 仰望奶牛#6，奶牛 #3 和 #6 没有仰望对象。

【数据规模】

对于的数据：；

对于的数据：。

解析

初看题目觉得这不是一个双循环就能解决的问题吗，但是超时在所难免。联系一下单调栈，每个单调栈的下标与最后的输出有一定的联系，因此使用单调栈来提速就有了可行性。于是我们从末尾开始向前遍历。

样例解析：

第一次取’2‘，’2‘下标入栈，而下一个比’2‘大的数的下标为栈的上一个元素‘0’（这里在栈开始之前加入了元素’0‘，因此不会越界）

第二次取’1‘，’1‘入栈，而下一个比’2‘大的数的下标为栈的上一个元素，即’2‘的下标’6‘。

第三次将上一个‘1’出栈，而这次的’1‘入栈，输出下标仍然是’6‘。

第四次将’2‘出栈，’6‘入栈，下标输出为’0’

代码如下：

#include<stdio.h>  
int a[100008];  
int stm[1000008]={0};  
int ans[1000008]={0};  
int main(){  
    int n;  
    int top=0;//栈初始化  
    scanf("%d",&n);  
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);  
    for(int i=n;i>=1;i--){  
        while(top>0&&a[i]>=a[stm[top]])top--;//退栈  
        ans[i]=stm[top];//记录  
        stm[++top]=i;//入栈  
    }  
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);  
    return 0;  
}

题目3：奶牛排队

题目描述

奶牛在熊大妈的带领下排成了一条直队。

显然，不同的奶牛身高不一定相同……

现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛是最矮的，最右边的是最高的，且高于奶牛。中间如果存在奶牛，则身高不能和奶牛相同。问这样的奶牛最多会有多少头？

从左到右给出奶牛的身高，请告诉它们符合条件的最多的奶牛数（答案可能是，但不会是）。

输入格式

第一行一个正整数，表示奶牛的头数。

接下来行，每行一个正整数，从上到下表示从左到右奶牛的身高。

输出格式

一行一个整数，表示最多奶牛数。

样例 #1

样例输入 #1

样例输出 #1

提示

样例解释

取第头到第头奶牛，满足条件且为最多。

数据范围

对于全部的数据，满足，。

解析

如果想要借用单调栈解决问题，就要抓住连续奶牛的最后一个比左边的奶牛都要高，第一个奶牛比右边的奶牛都要矮。

或许我们的第一反应是两个单调栈，但是仔细一想，其实我们只需要运用一个单调栈，找到第一个奶牛右边第一个不比它高的奶牛的下标k，在单调栈中找到比k小的最大的下标，即可确定连续奶牛的区间长度。

#include<stdio.h>  
long long int arr[100006];  
int stm[100006],id[100006];  
int judge(int);  
int main() {  
    int n;  
    int top = 0, ans = 0;  
    scanf("%d", &n);  
    for (int i = 1; i <= n; i++)scanf("%d", &arr[i]);  
    for (int i = n; i >= 1; i--) {  
        while (top > 0 && arr[i] >= arr[stm[top]])top--;  
        stm[++top] = i;//单调栈  
        int max = judge(top);  
        if (ans < max)ans = max;  
    }  
    printf("%d", ans);  
    return 0;  
}  
int judge(int t)  
{  
    if(t==1)return 0;//栈中只有一个元素无需判断  
    int k;  
    //找到下标为stm[top]为下标的数右侧比它小或与它相等的最小值
    for(k=stm[t]+1;k<=stm[1];k++){  
        if(arr[stm[t]]>=arr[k])break;  
    }  
    int m=t;  
    //找到范围内的栈
    while(k>stm[m-1]&&m>1)m--;  
    return stm[m]-stm[t]+1;  
}

补充：深刻了解了单调栈之后发现两个单调栈所花费的时间更少，但由于不想再回去AC就不放代码了。

题目：3 [COCI2010-2011#3] DIFERENCIJA

题目描述

给出一个长度为的序列，求出下列式子的值：

即定义一个子序列的权值为序列内最大值与最小值的差。求出所有连续子序列的权值和。

输入格式

输入第一行一个整数，表示序列的长度。

接下来的行，每行一个整数，描述这个序列。

输出格式

输出一行一个整数，表示式子的答案。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

样例 #3

样例输入 #3

样例输出 #3

提示

数据规模与约定

对于的数据，保证，。

说明

题目译自 COCI2010-2011 CONTEST #3 T5 DIFERENCIJA。

解析

对于题目中的式子可转化为：

根据这个思路，代码如下：

#include<stdio.h>  
int arr[300005];  
int stm1[300005];  
long long int idl[300005];  
long long int idr[300005];  
int main()  
{  
    int n;  
    long long int peak=0,bottom=0;  
    scanf("%d",&n);  
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]);  
    int top1=0;  
    for (int i = 1; i <= n; i++) {  
        while (top1 > 0 && arr[i] >= arr[stm1[top1]])top1--;  
        idl[i] = stm1[top1]; //位于左边比下标为i的数大的数的下标（没有则为0）
        stm1[++top1] = i;  
    }  
    top1=0;  
    for (int i = n; i >=1; i--) {  
        while (top1 > 0 && arr[i] > arr[stm1[top1]])top1--;  
        stm1[0]=n+1;  
        idr[i] = stm1[top1];  //位于右边不小于下标为i的数的数的下标（没有则为n+1） 
        stm1[++top1] = i;  
    }  
    for(int i=1;i<=n;i++){  
        peak+=((i-idl[i])*(idr[i]-i)-1)*arr[i];  
    }  
    top1=0;  
    stm1[0]=0;  
    for (int i = 1; i <= n; i++) {  
        while (top1 > 0 && arr[i] <= arr[stm1[top1]])top1--;  
        idl[i] = stm1[top1];  //位于左边比下标为i的数小的数的下标（没有则为0）
        stm1[++top1] = i;  
    }  
    top1=0;  
    for (int i = n; i >=1; i--) {  
        while (top1 > 0 && arr[i] < arr[stm1[top1]])top1--;  
        stm1[0]=n+1;  
        idr[i] = stm1[top1];  //位于右边不大于下标为i的数的数的下标（没有则为n+1）
        stm1[++top1] = i;  
    }  
    for(int i=1;i<=n;i++){  
        bottom+=((i-idl[i])*(idr[i]-i)-1)*arr[i];  
    }  
    printf("%lld",peak-bottom);  
    return 0;  
}

这里注意idr和idl数组开了long long int，因为在后面的计算可能会超出int范围。

计算机 > C语言

#算法学习

单调栈

http://example.com/posts/单调栈/

作者

晓寒

发布于

2022年11月12日

许可协议

深度优先搜索-DFS 上一篇

排序算法下一篇