浅谈单调队列

本文介绍一种基于队列的特殊数据结构——单调队列

基本原理

所谓单调队列，其首先是一个队列。只不过对于单调队列而言，其队列中的元素按照某种排序规则可以保证单调递增或单调递减。如果从队尾新入队的元素破坏了队列的单调性，则需要对队尾进行出队操作直到满足单调性为止。这里补充说明下，之所以采用某种排序规则的说法。是因为很多时候我们不是把元素直接进行入队的。而是选择把它在集合容器中的位置索引进行入队的。显然此时我们在操作队列时，比较的是位置索引所指向的元素。具体地，单调队列可细分为单调递增队列、单调递减队列

• 单调递增队列：队列内的元素按照某种排序规则可以保证从队首到队尾是单调递增的
• 单调递减队列：队列内的元素按照某种排序规则可以保证从队首到队尾是单调递减的

单调队列可以很好地解决RMQ区间最值查询问题。即对一维数组而言，计算任意长度为k的区间的最大值、最小值。具体地：

• 计算任意长度为k的区间的最小值使用单调递增队列
• 计算任意长度为k的区间的最大值使用单调递减队列

而在操作单调队列的过程中，主要包括以下几个步骤：

1. 对一维数组按从左到右的顺序进行遍历
2. 如果从队尾入队的当前元素破坏了队列的单调性，则需要对队尾进行出队操作直到满足单调性为止。具体地，对于单调递增队列而言，如果 队尾所对应的元素 大于 当前元素 就一直对队尾元素进行出队，直到满足单调性要求为止；对于单调递减队列而言，如果 队尾所对应的元素 小于 当前元素 就一直对队尾元素进行出队，直到满足单调性要求为止
3. 此时再将当前元素从队尾入队
4. 判断队头元素是否属于于当前区间，如果不存在则需要对队头元素进行出队。显然对于一个长度为k的区间而言，其区间范围为[i-k+1, i]。其中i为当前元素的索引下标
5. 此时队头元素所对应的值 就是 [i-k+1, i]区间 的最值
6. 重复Step 2 - Step 5，直到计算完所有区间为止

实践

学习过程中要善于理论联系实际。故在介绍完单调队列的基本原理后，现在我们来进行实践。这里以LeetCode的第239题——滑动窗口最大值为例

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值

示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

示例 2：
输入：nums = [1], k = 1
输出：[1]

本题是需要计算滑动窗口内的最大值，故可以使用单调递减队列进行解决

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int size = nums.length;
        int[] res = new int[ size-k+1 ];
        // 单调递减队列
        Deque<Integer> queue = new LinkedList<>();

        for (int i=0; i<size; i++) {
            int current = nums[i];
            // 当前元素破坏了队列的单调性, 则不对队尾元素进行出队操作
            while ( !queue.isEmpty() && nums[queue.peekLast()] < current ) {
                queue.removeLast();
            }

            // 当前元素从队尾入队
            queue.addLast( i );

            // 区间范围: [i+1-k, i]
            int leftIndex = i+1-k;
            if( leftIndex>=0 ) {
                // 队首元素不在当前区间范围内, 故移除
                while ( !queue.isEmpty() && queue.peekFirst()<leftIndex ) {
                    queue.removeFirst();
                }
                // 此时队首元素即为当前区间范围内的最大值
                res[leftIndex] = nums[ queue.peekFirst() ];
            }
        }

        return res;
    }
}