单调队列及其LeetCode应用详解
本博文所有的代码均可在 https://github.com/Hongze-Wang/LeetCode_Java https://github.com/Hongze-Wang/LeetCode_Python 中找到。
队列(Queue)是另一种操作受限的线性表，只允许元素从队列的一端进，另一端出，因此具有先进先出(FIFO)的特性。
单调队列(Monotonic Queue)是一种特殊的队列，它首先是一个队列，其次队列内部的元素单调递增(递增队列)或者单调递减(递减队列)。
注意：单调队列在算法应用中大多是基于双端队列(Deque)实现的，因为经常会涉及其他操作，而不是单单维护一个单调队列。。
单调队列在算法中的应用在于可以求区间内的最大或者最小值。
// 递增队列
for(int i=0; i<nums.length; i++) {
while(!deque.isEmpty() && deque.peekLast() <= nums[i]) {
deque.pollLast();
}
deque.offer(nums[i]);
}
// 递减队列
for(int i=0; i<nums.length; i++) {
while(!deque.isEmpty() && deque.peekLast() >= nums[i]) {
deque.pollLast();
}
deque.offer(nums[i]);
}在上面的单调队列中，访问到任一元素，队头peekFirst()保存的都是当前的最大值或者最小值(或者索引也可以)。
下面以实际的算法题说明递增队列的作用，这是一道字节算法面试题。
LeetCode 239. Sliding Window Maximum(hard)
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window. Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7Example 2: Input: nums = [1], k = 1 Output: [1] Example 3: Input: nums = [1,-1], k = 1 Output: [1,-1] Example 4: Input: nums = [9,11], k = 2 Output: [11] Example 5: Input: nums = [4,-2], k = 2 Output: [4] Constraints: 1 <= nums.length <= 105 -104 <= nums[i] <= 104 1 <= k <= nums.length
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new LinkedList();
int[] res = new int[nums.length-k+1];
for(int i=0; i<nums.length; i++) {
while(!deque.isEmpty() && deque.peekFirst() <= (i-k)) { // maintain the window size
deque.pollFirst();
}
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offer(i);
if(i+1 >= k) {
res[i+1-k] = nums[deque.peekFirst()];
}
}
return res;
}
}