单调栈和滑动窗口【题解】

全文目录

• 单调栈
• • 代码
• 滑动窗口（单调队列）
• • 代码

单调栈

单调栈，顾名思义就是具有单调性的栈。通常是用来求数组中的左边第一个比自身小或者大的数，使用场景还是比较有限的。但是对于解题还是有着很大的帮助的。

我们还是通过题目来进行讲解。

对于这种题目，首先想到的都是暴力求解：

枚举每一个位置，然后从这个位置的前一个位置元素遍历，找到第一个小于它的元素的位置就是我们所求的。

那么这时的时间复杂度就会是 O(n^2) 效率很低。

思路优化：

我们可以发现这不就是我们从前往后枚举，然后从后往前遍历么 —— 这就符合了栈的先进后出。那么就可以在从后往前遍历的时候构建一个单调栈，将大于它的数都出栈，那么这个栈就是一个单调递增的单调栈。

如果当前位置有解,这么这个解一定是栈顶的元素 —— 因为大于它的我们都弹栈了， 然后当前元素又入栈，我们发现，栈里面栈顶元素的解一定是栈顶元素下面的那个元素。

利用这个性质,我们比较时就可以跳过许多不需要比较的位置了。

比如我们现在要入栈的是 8， 然后栈顶元素是 7， 那么答案一定是 7， 因为 7 一定是最后入栈的。如果栈顶元素是 9，那么 9 弹出，此时栈顶是 6， 那么答案就是 6， 因为 6 一定是距离 9 最近的并且小于它的元素。其他位置的元素要么大于 9， 要么距离远，都不符合条件。

代码

#include <iostream>

using namespace std;

const int N = 100010;
int a[N], n, tt;


int main()
{
    tt = -1;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        
        while (tt > -1 && a[tt] >= x) tt--;	// 将栈顶大于a[i]的数出栈，保持单调性
        if (tt == -1) cout << -1 << ' ';
        else cout << a[tt] << ' ';
        a[++tt] = x;	
    } 
    return 0;
}

滑动窗口（单调队列）

暴力求解：

我们还是先来看一下使用暴力求解的做法：

枚举每个区间，然后在区间中寻找最大值和最小值。

这时的时间复杂度就是 O(n * k) 效率还是比较低的。

思路优化（最小值为例）：

我们可以根据暴力求解的规律发现，每个元素都是先进先出的 —— 满足队列的性质，那么我们就可以通过队列来维护每一个区间。

如果队列中存在两个元素，满足 a[i] >= a[j] 且 i < j，那么无论在什么时候我们都不会取a[i]作为最小值了（因为 j 比 i 活得久），所以可以直接将 a[i] 删掉。

此时队列中剩下的元素严格单调递增，所以队头就是整个队列中的最小值，可以用 O(1) 的时间找到。

为了维护队列的这个性质，我们在往队尾插入元素之前，先将队尾大于等于当前数的元素全部弹出即可。

这样所有数均只进队一次，出队一次，所以时间复杂度是 O(n) 的。

代码

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int a[N], q[N];     // q只是用来维护a的队列，存放的是下标
int head, tail = -1;
int n, k;

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
        
    // 寻找最小值
    // 先移动左端点，后移动右端点
    for (int i = 0; i < n; i++)
    {
        // 因为确定了每次只往后移动一位，所以用if
        // 当队列中有元素，并且队头的元素小于区间的左端点的时候右移
        if (tail >= head && i - k + 1 > q[head]) head++;
        
        // 找最小值，需要使用递增队列
        // 通过观察到的规律进行单调性的维护
        while (tail >= head && a[q[tail]] >= a[i]) tail--;
        q[++tail] = i;
        
        if (i >= k - 1) cout << a[q[head]] << ' ';  // 控制区间输出
    }
    puts("");
    
    head = 0, tail = -1;
    for (int i = 0; i < n; i++)
    {
        if (tail >= head && i - k + 1 > q[head]) head ++;
        while (tail >= head && a[q[tail]] <= a[i]) tail --; // 只需要改变队列的递增性质
        q[++tail] = i;
        
        if (i >= k - 1) cout << a[q[head]] << ' ';
    }
    
    
    return 0;
}