Simple java method using priorityQueue without creating new comparator, with explanation


  • 3
    H
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) {
            int[] store = {};
            return store;
        }
        if (nums.length <= k) {
            int[] store = new int[1];
            Arrays.sort(nums);
            store[0] = nums[nums.length - 1];
            return store;
        }
        int[] store = new int[nums.length - k + 1];
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            pq.add(-nums[i]);
        }
        store[0] = -pq.peek();
        for (int i = k; i < nums.length; i++) {
            pq.remove(-nums[i - k]);
            pq.add(-nums[i]);
            store[i-k+1] = -pq.peek();
        }
        return store;
    }
    

    since the element we want to order is just number, we can use the default comparator. However, the default comparator will peek the smallest element. Thus, we add the opposite number to the queue and return the opposite number of peeked element


  • 0
    D

    Hi, you are using

    pq.remove(-nums[i - k]);
    its not linear complexity.
    actually your solution is O(n*n)


  • 0
    J

    I think it should be nlogk


  • 0
    T

    @dennis10 it's an invariant for most of the execution that pq is of size k, it is <=k at the beginning and end. You're right here that n*k degrades to n*n worst case, but saying that all cases are is overestimation, similar to saying that this algorithm is also O(2^n).

    @Jesse_xu PriorityQueue uses a heap, which only keeps tabs on the min element, there's nothing else known about positions of other numbers. So removing an arbitrary number needs a full scan.

    remove is k+logk (see source of PriorityQueue.remove method), add is logk, so the runtime is about k*logk + (n-k+1) * (k+logk + logk) (add first k + remaining nums * (remove + add)), worse than counting the max for each window separately... in (n-k+1) * k steps.

    @hello_today_ That nums.length <= k is unnecessary, the problem stated that k will be valid and the n==k. case is already handled by your code. Anyway sorting is an expensive O(n logn) operation, you can find the single max value with a simple linear scan in those exceptional cases...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.