239. Sliding Window Maximum 发表于 2021-12-18 Priority Queue12345678910111213141516171819202122232425262728293031323334353637class Solution { private static class Element { private final int value; private final int index; public Element(int value, int index) { this.value = value; this.index = index; } } public int[] maxSlidingWindow(int[] nums, int k) { if (nums.length == 0) { return new int[0]; } int[] res = new int[nums.length - k + 1]; Queue<Element> maxHeap = new PriorityQueue<>((o1, o2) -> o2.value - o1.value); for (int i = 0; i < k - 1; i++) { maxHeap.offer(new Element(nums[i], i)); } for (int j = k - 1; j < nums.length; j++) { maxHeap.offer(new Element(nums[j], j)); int i = j - k + 1; // window: [i, j] int evictedIndex = i - 1; while (maxHeap.peek().index <= evictedIndex) { maxHeap.poll(); } res[j - k + 1] = maxHeap.peek().value; } return res; }} Monotonic Queue12345678910111213141516171819202122232425262728class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int[] res = new int[nums.length - k + 1]; // 非严格单调递增队列,允许包含重复值,first -> ... -> last Deque<Integer> increaseDeque = new LinkedList<>(); for (int i = 0; i < nums.length; i++) { int num = nums[i]; while (!increaseDeque.isEmpty() && num > increaseDeque.getFirst()) { // 当前 num 比队首元素大,则队首元素可以安全移除,因为更大的元素出现了 increaseDeque.removeFirst(); } increaseDeque.addFirst(num); // 将当前元素添加至队首 int evictedIndex = i - k; if (evictedIndex >= 0 && increaseDeque.getLast() == nums[evictedIndex]) { increaseDeque.removeLast(); } if (i >= k - 1) { // 此时可以收集最大值 res[i - k + 1] = increaseDeque.getLast(); } } return res; }} Reference239. Sliding Window Maximum剑指 Offer 59 - I. 滑动窗口的最大值