LeetCode link

Intuition

  • Using a heap to maintain the index, remove and add the borders, and add the peek value to the final result.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length < 1 || k  < 1 || k > nums.length) {
            return new int[0];
        }
        int[] result = new int[nums.length - k + 1];
        Comparator<Integer> comparator = new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                return nums[b] - nums[a];
            }
        };
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(comparator);
        for (int i = 0; i < k; i++) {
            minHeap.add(i);
        }
        result[0] = nums[minHeap.peek()];
        for (int i = 1; i + k - 1 < nums.length; i++) {
            minHeap.remove(i - 1);
            minHeap.add(i + k - 1);
            result[i] = nums[minHeap.peek()];
        }
        return result;
    }
}

Follow Up

Solve in linear time.

solution

  • Using deque to maintain the index of large numbers in descending.
  • When the head is beyond the window range, delete it.
  • When the incoming number is larger than the tail, then poll the tail, until the number is smaller than the tail or the deque is empty.
  • The head is the largest number in the current window.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length < 1 || k  < 1 || k > nums.length) {
            return new int[0];
        }
        int[] result = new int[nums.length - k + 1];
        LinkedList<Integer> deque = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            if (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.add(i);
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peek()];
            }
        }
        return result;
    }
}