单调队列及其用法

1. 单调队列

单调队列是一种特殊的队列数据结构，它在处理特定类型的算法问题时非常有用，特别是那些涉及滑动窗口的问题。在单调队列中，元素按照某种单调性（单调递增或单调递减）排列。这意味着队列的元素要么是按照非递增的顺序排列，要么是按照非递减的顺序排列。

单调队列的主要特点和应用如下：

1. 单调性:

   • 在单调递增队列中，队头是最小元素，队尾是最大元素。
   • 在单调递减队列中，队头是最大元素，队尾是最小元素。

2. 应用场景:

   • 单调队列通常用于解决滑动窗口类型的问题，如在一系列数值中寻找每个窗口的最大值或最小值。
   • 它可以在O(1)的时间复杂度内提供窗口的最大或最小值，这使得整体算法效率非常高。

3. 操作:

   • 入队（Enqueue）操作：当新元素入队时，队列会从队尾开始，移除所有破坏队列单调性的元素，然后将新元素添加到队尾。
   • 出队（Dequeue）操作：当元素需要从队头出队时，只需要将队头元素移除。如果出队元素是当前窗口的最大（或最小）值，那么下一个元素自然成为新的最大（或最小）值。

4. 实现:

   • 单调队列可以用双端队列（Deque）来实现。双端队列允许从两端快速添加和移除元素，适合实现单调队列的操作。

5. 优势:

   • 单调队列的优势在于其高效处理滑动窗口内最大值或最小值查询的能力，特别是在这些查询需要频繁进行，且窗口大小动态变化的情况下。

综上所述，单调队列是解决滑动窗口及相关问题的强大工具，它通过保持元素的单调性来优化查询效率，特别是在需要频繁查询窗口内的最大或最小值时。

2. 滑动窗口相关问题

使用单调队列解决滑动窗口问题的主要思路是利用队列的单调性来快速获得窗口内的最大值或最小值。这种方法特别适用于那些要求在一个数组或列表上对每个固定大小的连续子数组（窗口）进行某种计算的问题。以下是使用单调队列解决滑动窗口问题的基本步骤：

1. 定义单调队列:

   • 创建一个双端队列（Deque），用于存储窗口中的元素的索引。这个队列将保持单调递增或单调递减的顺序，具体取决于问题是求窗口内的最大值还是最小值。

2. 处理新元素:

   • 当新元素准备进入窗口时（例如，遍历数组），先从队尾开始，移除所有破坏队列单调性的元素。对于最大值问题，移除所有小于新元素的队尾元素；对于最小值问题，则移除所有大于新元素的队尾元素。

3. 维持窗口大小:

   • 确保队列中只包含当前窗口内的元素。如果队头元素已经不在窗口内（例如，其索引小于当前窗口的起始索引），则将其从队头移除。

4. 查询窗口值:

   • 在每个窗口上，队列的头部元素（最前面的元素）就是该窗口的最大值或最小值（取决于队列是单调递增还是单调递减）。

5. 更新和输出结果:

   • 根据具体问题的需求，可能需要记录每个窗口的最大值或最小值，或进行其他相关计算。

举个例子，假设你有一个数组 [4, 3, 5, 2, 6, 2, 3]，并且你需要找到每个大小为3的窗口的最大值。你可以使用一个单调递减队列，每次移动窗口时，确保队列的头部元素是该窗口的最大值。当你从左到右遍历数组时，队列首先填充 [4]，然后变成 [4, 3]，接着是 [5]（因为4和3小于5，被移除），以此类推。每次窗口移动时，队列的头部元素就是当前窗口的最大值。

这种方法的优势在于其时间复杂度。对于每个元素，入队和出队操作平均只需要常数时间（O(1)），因此整个算法的时间复杂度是线性的（O(n)），其中n是数组或列表的长度。

算法实现：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }
}