单调队列与单调栈


单调队列与单调栈

    最近我学习了单调队列和单调栈,虽然是基本的知识点,我还是要总结一下。


队列与栈

    在大一的数据结构课上,我学习了队列与栈的实现,既有链式结构实现,也有顺序结构实现。两者各有优缺点,顺序结构只能使用在数据范围大小已经确定的情况下,而链式结构采用动态内存分配,无需事先知道数据大小,但是链式结构实现比顺序结构复杂一些,且运行效率上也要比顺序结构的差。而在算法竞赛中,数据大小很多时候都已经确定,比赛时间紧,所以使用顺序结构居多。实现就不贴了,太简单了,贴了丢人。自行百度


单调栈

    单调栈,顾名思义,单调的栈。也就是 该栈中的元素需要维持自顶向下是由大变小(或者由小变大)的状态。 那么维持这样的状态有什么用呢?这样我们就可以判断 该栈中的每一个元素 它左边离它最近的比它小(大)的元素 和 它右边离它最近的比它小(大)的元素 的位置。 分别可以用自顶向下单调递减栈 和 自顶向下单调递增栈 实现。
贴一个单调递减栈,顺序结构实现:

/*自顶向下单调递减栈*/
#define STACK_MAXSIZE 50000
int s[STACK_MAXSIZE];
void monotonousStack(int *arr, int len)
{
    int top = 0;    //指向栈顶位置的变量
    for(int i = 0; i < len; i++)
    {
        /*
        如果栈中存在元素,且当前需要入栈的元素小于等于栈顶元素,
        则弹出栈顶元素,直到栈空或者需要入栈的元素大于栈顶元素。
        */
        while(top > 0 && arr[s[top]] >= arr[i])
            top--;

        /*将下标入栈*/
        s[top++] = i;
    }
}

    这个模板目前只是维持了栈的单调,没有任何用途。要想 灵活运用 它,我们需要理解 每个元素在栈中操作时发生的状态变化。我的切入点是, 观察每个元素弹出栈时的栈的状态 。当一个元素 被迫 弹出栈时,也就是这个元素在 栈顶 位置,有一个小于等于它的元素需要入栈。此时需要入栈的元素小于等于栈顶元素,所以栈顶元素需要弹出。在这个状态下,我们得知栈顶元素(即将弹出的元素)在栈中的下面一个元素,是 它左边离它最近的比它小的元素 (在原序列中的下标, 也就是得到了它的位置), 而迫使它弹出的那个元素,就是 它右边离它最近的比它小的元素(在原序列中的下标, 也就是得到了它的位置)


例题

    我的这篇笔记其实是我对这个知识点的一点理解,如果你想学习单调栈的话,建议看一下 OI Wiki 上的讲解,看懂了在来看看我写的,可能还有点意义。下面看一下一个简单的例题(poj2796点我传送):

    比尔正在开发一种新的人类情感数学理论。他最近的调查致力于研究好或坏的日子是如何影响人们对人生某个时期的记忆的。比尔最近提出了一个新想法,即给人类生命中的每一天赋一个非负整数。比尔称这种价值为“一天的情感价值”。情感价值越大,日子就越美好。比尔认为,人一生中某一时期的价值与给定时期内的情感价值乘以该时期内最小的情感价值的总和成正比。这个模式反映出,一个非常糟糕的日子可能会极大地破坏平均时期的良好。现在比尔计划调查他自己的生活,找出他生命中最有价值的时期。帮助他这样做。

原题是洋文,以上为网易有道翻译的结果。
题解 :
题目要我们找生命中最有价值的时期,那我们 枚举每一天(假设有N天),把这一天当作最小的情感价值时,其对应时期的范围 。可以得到一个总和,总共可以得到N个总和。那么这N个中最大的那个总和即为答案。那么题目给的感情值序列可以作为元素,依次入 自顶向下单调递减栈 ,当入栈的元素被迫弹出的时候,就是把这一天当作最小值进行计算的时候。为了让所有的元素都被能 被迫 弹出,我在感情序列最后添加了一个值 -1 ,这样就可以让所有元素都能 被迫 弹出。然后为了减少重复运算,防止出现超时,我们建一个sum[]数组,对情感序列进行前缀和。
AC代码如下:

#include <stdio.h>
int arr[100005], s[100005];
long long sum[100005];
int main(void)
{
    int n, i, j;
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
        scanf("%d", arr + i);
    arr[n + 1] = -1;    //在后面添加一个-1
    int top = 0, left = 1, right = 1;
    long long greatValue = 0;
    for(i = 1; i <= n + 1; i++)
    {
        sum[i] = sum[i - 1] + arr[i];   //前缀和
        /*维护单调栈*/
        while(top > 0 && arr[i] <= arr[s[top - 1]])
        {
            /*当栈顶元素需要弹出时,会进入该代码块*/
            long long temp = (sum[i - 1] - sum[s[top - 2]]) * arr[s[top - 1]];
            if(temp > greatValue){
                greatValue = temp;
                left = s[top - 2] + 1;
                right = i - 1;
            }
            top--;
        }
        s[top++] = i;
    }
    printf("%lld\n%d %d\n", greatValue, left, right);
    return 0;
}

单调队列

    我觉得单调队列是单调栈功能的升级,单调队列可以指定范围。只要理解了单调栈的维护过程,单调队列的特性也能很快的理解。
贴一下 自头到尾单调递增 的单调队列实现:

#define QUEUE_SIZE 50000
int q[QUEUE_SIZE];
void monotonousQueue(int *arr, int len, int k)
{
    int front = 0, rear = 0;
    for(int i = 0; i < len; i++)
    {
        /*
        如果队列中存在元素,且当前需要入队尾的元素小于等于队列尾部元素,
        则让队尾元素出队,直到队列空或者需要入队尾的元素大于队尾元素。
        */
        while(front < rear && arr[q[rear]] >= arr[i])
            rear--;
        /*将下标存入队尾*/
        q[rear++] = i;

        /*限制范围*/
        while(q[front] < i - k)
            front++;
    }
}

这个模板暂时也没什么作用,就是用来,维护队列的单调的。

例题

来贴一道模板题 Sliding Window poj2823点我传送

    给出了一个大小为n≤10^6的数组。有一个大小为k的滑动窗口它从数组的最左边移动到最右边。你只能在窗口中看到k个数字。每次滑动窗口向右移动一个位置。下面是一个例子:数组为[1 3 -1 -3 5 3 6 7],k为3。您的任务是确定滑动窗口中每个位置的最大值和最小值。

题解:
没什么说的,就是建两个单调队列,一个自头到尾单调递减,一个自头到尾单调递增。分别求出每个元素在限制范围内的最大值和最小值。
上AC代码:

//poj2823 单调队列 用C++交就能过,不要用G++
#include <stdio.h>
int arr[1000005], q[1000005];
void solve(int n, int k)
{
    int i;
    int front = 0, rear = 0;
    for(i = 1; i < k; i++)
    {
        while(front <= rear && arr[q[rear]] >= arr[i])  rear--;
        q[++rear] = i;
    }
    for(i = k; i <= n; i++)
    {
        while(front <= rear && arr[q[rear]] >= arr[i])  rear--;
        q[++rear] = i;
        while(q[front] <= i - k)   front++;
        printf("%d ", arr[q[front]]);
    }
    printf("\n");
    front = 0;  rear = 0;
    for(i = 1; i < k; i++)
    {
        while(front <= rear && arr[q[rear]] <= arr[i])  rear--;
        q[++rear] = i;
    }
    for(i = k; i <= n; i++)
    {
        while(front <= rear && arr[q[rear]] <= arr[i])  rear--;
        q[++rear] = i;
        while(q[front] <= i - k)   front++;
        printf("%d ", arr[q[front]]);
    }
    printf("\n");
}
int main(void)
{
    int n, k, i;
    scanf("%d%d", &n, &k);
    for(i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    solve(n, k);
    return 0;
}

声明:Trikker的小破站|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 单调队列与单调栈


分享一些学习成果