239. Sliding Window Maximum

三刷 07/2022

Version #1 Sliding Window

一遍bug free

上次相等时候不应该poll last出来的错误这次没犯

Time O(N)

Space O(k) - the deque containing at most k characters

Runtime: 41 ms, faster than 83.35% of Java online submissions for Sliding Window Maximum.

Memory Usage: 140.5 MB, less than 73.80% of Java online submissions for Sliding Window Maximum.

class Solution {

    public int[] maxSlidingWindow(int[] nums, int k) {

        Deque<Integer> deque = new ArrayDeque<>();

        // 1, 2, 3  k = 2

        // 

        int[] result = new int[nums.length - k + 1];

        int start = 0;

        for (int end = 0; end < nums.length; end++) {

            while (!deque.isEmpty() && deque.peekLast() < nums[end]) {

                deque.pollLast();

            }

            deque.offerLast(nums[end]);

            if (end - start + 1 == k) {

                result[start] = deque.peekFirst();

                if (deque.peekFirst() == nums[start]) {

                    deque.pollFirst();

                }

                start++;

            }

        }

        return result;

    }

}

二刷 06/2022

写了一个bug就是当当前值和que.peekLast相等的时候要不要pollLast，答案是不要

举个例子

因为在pollFirst的时候是根据数值remove的

所以需要存duplicate的最大值

[-7,-8,7,5,7,1,6,0]
4

Time O(N)

Space O(k)

class Solution {

    public int[] maxSlidingWindow(int[] nums, int k) {

        // [1,3,-1,-3,5,3,6,7]

        // We have a queue, whenever we see a number, we can poll out all elements smaller than current number from the tail of the queue, since we've already have a number larger and will never be removed from the window before those smaller elements

        Deque<Integer> deque = new ArrayDeque<>();

        // 0   1  2

        // [1, 2, 3] k = 2

        // (    )

        //    (    )

        int[] max = new int[nums.length - k + 1];

        for (int i = 0; i < nums.length; i++) {

            while (!deque.isEmpty() && nums[i] > deque.peekLast()) {

                deque.pollLast();

            }

            deque.addLast(nums[i]);

            // remove the element that's out of the window

            if (i - k >= 0 && deque.peekFirst() == nums[i - k]) {

                deque.pollFirst();

            }

            if (i - k + 1 >= 0) {

                max[i - k + 1] = deque.peekFirst();

            }

        }

        return max;

    }

}

一刷

Version #2 Deque
Time O(n)
Space O(k)

64.14 %
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //            start    end      end - start == k - 1
        // index i  0  1  2  3  4  5
        // nums[i]
        if (nums == null || nums.length == 0) return nums;
       
        // When a number x comes after current max number
        // 1. x >= currMax -> currMax can be replaced by x
        // 2. x < currMax -> it is possible that x is usefull after currMax is passed
        // However, every candidate that is smaller than x will be useless
        // --> candidates before x are all larger than x, currMax is larger than all candidates
        Deque<Integer> candidates = new ArrayDeque<>();
        int[] result = new int[nums.length - k + 1];
        int start = 0;
        for (int end = 0; end < nums.length; end++) {
            if (end - start == k) {
                if (nums[start] == candidates.peekFirst()) {
                    candidates.pollFirst();
                }
                start++;
            }
            // add nums[end]
            while (!candidates.isEmpty() && candidates.peekLast() < nums[end]) {
                candidates.pollLast();
            }
            candidates.offerLast(nums[end]);
            if (end - start == k - 1) result[start] = candidates.peekFirst();
        }
        return result;
    }
}


Version #1 Simply remove
15.42 % 
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return nums;
        int[] result = new int[nums.length - k + 1];
        PriorityQueue<Integer> pq = new PriorityQueue<>(10, new Comparator<Integer>() {
            @Override
            public int compare(Integer i1, Integer i2) {
                return i2 - i1;
            }
        });
        for (int i = 0; i < nums.length; i++) {
            pq.add(nums[i]);
            //remove last element
         
            if (i >= k - 1) {
                if (i >= k) pq.remove(nums[i - k]);
                result[i - k + 1] = pq.peek();
            }
         
        }
        return result;
    }
}