给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。
例如,如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3,那么一共存在 6 个滑动窗口,他们的最大值分别为 {4, 4, 6, 6, 6, 5}。
import java.util.*;
import java.lang.*;
public class Solution {
public ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> res = new ArrayList<>();
if(num.length == 0 || size == 0)
return res;
Deque<Integer> q = new LinkedList<>();
int index = 0;
for(int i = 0; i < num.length; i++) {
// 队列存下标,控制出队的几种情况 1 3 -1 -3 5
// q[3 -1 -3 5]出3
if(q.size() > 0 && i - q.peekFirst() >= size)
q.pollFirst();
// q[-1 -3 5]出 -3 -1
while(q.size() > 0 && num[i] > num[q.peekLast()])
q.pollLast();
q.add(i);
// 最大值放入
if(i >= size - 1)
res.add(num[q.peekFirst()]);
}
return res;
}
}
public ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> ret = new ArrayList<>();
if (size > num.length || size < 1)
return ret;
PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1); /* 大顶堆 */
for (int i = 0; i < size; i++)
heap.add(num[i]);
ret.add(heap.peek());
for (int i = 0, j = i + size; j < num.length; i++, j++) { /* 维护一个大小为 size 的大顶堆 */
heap.remove(num[i]);
heap.add(num[j]);
ret.add(heap.peek());
}
return ret;
}