跳转至

单调队列

154. 滑动窗口

给定一个大小为 \(n \leq 10 ^ 6\) 的数组。

有一个大小为 \(k\) 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 \(k\) 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]，\(k\) 为 \(3\)。

窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

单调队列，顾名思义队列里面的元素是单调排列的。对于该题，就考虑一个窗口：[1 3 -1] -3 -5 3 6 7 当前窗口的最大值一定是 3 ，我们可以丢弃 1 吗？随着窗口的向右移动，1 一定无法作为窗口的最大值输出的，因为有更靠右的、更大的 3 可以选择；-1 可以丢弃吗，不可以随着窗口的向右移动，3 是可以被踢出窗口的，-1 只能作为最大值预备军保留在窗口中。

因此这道题我们只需要不断地维护一个单调递减的队列就行，插入新数据 \(x\) 时，如果队尾的数据比当前插入的数据 \(x\) 还要小或者等时，直接踢出队列，直到队尾数据大于 x 为止才能插入，对于队头的处理，由于该队头有可能已经不在窗口中了，所以要将不在窗口中滞留的最大值踢出队列，做好上面的所有工作后，队头元素就是窗口的最大值。

STL 双端队列 deque
  1. push_back : 队列尾部插入数据
  2. push_front : 队列头部插入数据
  3. pop_back : 队列尾部抛弃数据
  4. pop_front : 队列头部抛弃数据
  5. back : 返回队列尾部的值
  6. top : 返回队列头部的值
  7. size : 返回队列长度
  8. empty : 返回队列是否为空
154. 滑动窗口 - 代码参考 
// 即使是不成熟的尝试，

const int N = int (1e7 + 10);
int n, m;
int q[N];

deque<vector<int>> mi, mx;
queue<int> ax, ai;

void solve(void)
{
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf ("%d", q + i);
    for (int i = 1; i < m; i ++) 
    {
        while (mx.size() && mx.back()[0] <= q[i]) mx.pop_back();
        while (mi.size() && mi.back()[0] >= q[i]) mi.pop_back();
        mx.push_back({q[i], i}); mi.push_back({q[i], i});
    }
    for (int i = m; i <= n; i ++)
    {
        while (mx.size() && mx.back()[0] <= q[i]) mx.pop_back();
        while (mi.size() && mi.back()[0] >= q[i]) mi.pop_back();
        mx.push_back({q[i], i}); mi.push_back({q[i], i});
        while (mx.front()[1] < i - m + 1) mx.pop_front();
        while (mi.front()[1] < i - m + 1) mi.pop_front();
        ax.push(mx.front()[0]); ai.push(mi.front()[0]);
    }
    while (ai.size()) { printf ("%d ", ai.front()); ai.pop(); } puts("");
    while (ax.size()) { printf ("%d ", ax.front()); ax.pop(); } puts("");
}

// 也胜于胎死腹中的策略。