提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
前言
现在需要一种新的队列结构，既能够维护队列元素「先进先出」的时间顺序，又能够正确维护队列中所有元素的最值，这就是「单调队列」结构。
一、力扣503. 下一个更大元素 II
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] arr = new int[2*n];
int[] res = new int[n];
for(int i = 0; i < 2*n; i ++){
if(i < n){
arr[i] = nums[i];
}else{
arr[i] = nums[i-n];
}
}
Deque<Integer> deq = new LinkedList<>();
for(int i = 2*n-1; i >= 0; i --){
while(!deq.isEmpty() && deq.peekLast() <= arr[i]){
deq.pollLast();
}
if(i < n){
res[i] = deq.isEmpty() ? -1 : deq.peekLast();
}
deq.offerLast(arr[i]);
}
return res;
}
}
二、力扣239. 滑动窗口最大值
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
MonotonicDeque mq = new MonotonicDeque();
List<Integer> list = new ArrayList<>();
for(int i = 0; i < nums.length; i ++){
if(i < k-1){
mq.push(nums[i]);
}else{
mq.push(nums[i]);
list.add(mq.getMax());
mq.remove(nums[i-k+1]);
}
}
int[] res = new int[list.size()];
for(int i = 0; i < list.size() ; i ++){
res[i] = list.get(i);
}
return res;
}
class MonotonicDeque{
LinkedList<Integer> deq;
public MonotonicDeque(){
this.deq = new LinkedList<Integer>();
}
public void push(int x){
while(!deq.isEmpty() && deq.getLast() < x){
deq.pollLast();
}
deq.addLast(x);
}
public int getMax(){
return deq.getFirst();
}
public void remove(int x){
if(!deq.isEmpty() && deq.getFirst() == x){
deq.pollFirst();
}
}
}
}
