单调队列
队列(Queue)是另一种操作受限的线性表，只允许元素从队列的一端进，另一端出，因为具有先进先出(FIFO)的特性。
单调队列(Monotonic Queue)是一种特殊的队列，它首先是一个队列，其次队列内部的元素单调递增(递增队列)或者单调递减(递减队列)。
注意：单调队列是基于双端队列(Deque)实现的。
单调队列在算法中的应用在于可以求区间内的最大或者最小值。
// 递增队列
for(int i=0; i<nums.length; i++) {
while(!deque.isEmpty() && deque.peekLast() <= nums[i]) {
deque.pollLast();
}
deque.offer(i);
}
// 递减队列
for(int i=0; i<nums.length; i++) {
while(!deque.isEmpty() && deque.peekLast() >= nums[i]) {
deque.pollLast();
}
deque.offer(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:
Example 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;
}
}腾讯云开发者
