MaxHeap O(nlogn) solution


  • 0
    J

    The idea is only remove previous max value that will interfere with the current max.
    Every node will only be visited at most twice(add or remove). Thus the time complexity is O(nlogn).

    private class Node {
            private int num;
            private int index;
            
            public Node(int num, int index) {
                this.num = num;
                this.index = index;
            }
        }
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums.length == 0) return new int[0];
            Queue<Node> pq = new PriorityQueue<>(k, new Comparator<Node>() {
                @Override
                public int compare(Node a, Node b) {
                    return b.num - a.num;
                }
            });
            for (int i = 0; i < k; i++) {
                pq.offer(new Node(nums[i], i));
            }
            int[] res = new int[nums.length - k + 1];
            res[0] = pq.peek().num;
            for (int i = k; i < nums.length; i++) {
                //All nodes corresponding to the previous must be
                //deleted to not interfere with the current calculation. 
                while (!pq.isEmpty() && pq.peek().index <= i - k) {
                    pq.poll();
                }
                pq.offer(new Node(nums[i], i));
                res[i - k + 1] = pq.peek().num; 
            }
            return res;
        }
    

Log in to reply
 

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