单调队列
# 239. 滑动窗口最大值 (opens new window)
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums==null || nums.length<2)
return nums;
LinkedList<Integer> que = new LinkedList<>();// 单调减队列
int[] ret = new int[nums.length-k+1];
for(int i=0;i<nums.length;i++){
while(!que.isEmpty() && nums[que.peekLast()]<=nums[i])
que.pollLast();
que.addLast(i);
// 超过窗口
if(que.peek()<=i-k)
que.poll();
if(i-k+1>=0)
ret[i-k+1] = nums[que.peek()];
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 2487. 从链表中移除节点 (opens new window)
方法一：单调队列
class Solution {
public ListNode removeNodes(ListNode head) {
LinkedList<ListNode> que = new LinkedList<>();
ListNode node = head;
while(node!=null){
while(!que.isEmpty() && que.peekLast().val<node.val){
que.pollLast();
}
que.offerLast(node);
node = node.next;
}
ListNode newHead = que.poll();
ListNode p = newHead;
while(!que.isEmpty()){
p.next = que.poll();
p = p.next;
}
return newHead;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
方法二：递归
1