My Java Solution Using PriorityQueue


  • 11
    O

    Not a linear solution, instead, it is of O(nlogk) complexity, since add, pop and remove operation of PriorityQueue cost O(logk) time.

    What we need to do is just maintain a heap, that heap top gets the maximal value of the k elements.
    Since we know which element is removed and which is added to the queue, the solution seems easy to understand.

    public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int[] result = new int[len - k + 1];
        if(nums.length == 0) return new int[0];
        Queue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
            @Override
            public int compare(Integer i1, Integer i2){
                return Integer.compare(i2, i1);
            }
        });
        
        for(int i = 0; i < k; i ++){
            queue.add(nums[i]);
        }
        result[0] = queue.peek();
        for(int i = k; i < len; i ++){
            queue.remove(nums[i - k]);
            queue.add(nums[i]);
            result[i - k + 1] = queue.peek();
        }
       
        return result;
    }
    

    Could somebody suggest some linear solutions? The hint of using deque seems not that reasonable. We still need to maintain the k elements in the window in order.

    Thank you,


  • 0
    G

    You don't need all the window in the priority queue. Instead, you could just add the elements bigger than queue.peek().

    But, still not linear. You'd end up in O(n log c) c being a constant that could be k in the worst case:

    [2, 3, 4, 5 ,6 ,7 ,8] , 3


  • 0
    G

    not sure how remove works. [1,3,2,2,2,1], k =3, how would your suggestion work in this example?


  • 12
    D

    I don't know how priority queue approach passed the test cases, but unfortunately PriorityQueue.remove takes linear time rather than log(n) time. So the overall time complexity of priority queue approach should be O(n*k).

    In order to achieve linear time you need MaxQueue. You might want to take a look at this: http://stackoverflow.com/a/14130234


  • 4
    L

    Linear solution here :)

    The idea is that we only maintain a descending list for window. Each time we add a element, we remove all the elements smaller that it since they would never influence the MAX. So the 1st element in the arraylist is always the maximum. When we move window one step right, if the left most element is not the MAX, do nothing, otherwise delete the 1st element in the descending list. In total the descending list would add and delete elements for N times, so this algorithm is amortized linear.

    public class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums.length==0) return new int[0];
            List<Integer> descList = new ArrayList<Integer>();
            int[] res = new int[nums.length+1-k];
            for(int i=0;i<k-1;i++) addDescList(descList,nums[i]);
            for(int i=0;i<res.length;i++){
                addDescList(descList,nums[i+k-1]);
                res[i] = descList.get(0);
                if(nums[i]==descList.get(0)) descList.remove(0); //to delete the left most.
            }
            return res;   
        }
        public void addDescList(List<Integer> descList, int num){
            while(!descList.isEmpty()&&num>descList.get(descList.size()-1)) descList.remove(descList.size()-1);
            descList.add(num);
        }  
    }

  • 1
    E

    remove() is O(Log(k)), but remove(Object) is O(k) sadly. I had the same idea at first...


  • 1
    S

    A linear solution using the approach mentioned here: -

    http://stackoverflow.com/questions/8031939/finding-maximum-for-every-window-of-size-k-in-an-array

    The second answer using Dynamic Programming.

    My code, let me know if there is any difficulty in understanding. Thank you.

    public static int[] maxSlidingWindow(int[] nums, int k) {
    	if(nums == null || nums.length == 0) {
    		return new int[]{};
    	}
    
    	int length = nums.length;
    	int[] leftMax = new int[length];
    	int[] rightMax = new int[length];
    	leftMax[0] = nums[0];
    	rightMax[length - 1] = nums[length - 1];
    
    	for(int i = 1; i < length; ++i) {
    		leftMax[i] = (i % k == 0) ? nums[i] : Math.max(leftMax[i-1], nums[i]);
    		rightMax[length - 1 - i] = ((length - 1 - i) % k == 0) ? nums[length - 1 - i] : 
    			Math.max(rightMax[length - i],nums[length - 1 - i]);
    	}
    	int[] res = new int[length - k + 1];
    
    	for(int i = 0; i < length - k + 1; ++i) {
    		res[i] = Math.max(leftMax[i + k - 1], rightMax[i]);
    	}
    	return res;
    }
    

  • 0
    D

    My solution is the same as yours.

    public class Comp implements Comparator<int[]> {
        @Override
        public int compare(int[] a, int[] b) {
            return b[1] - a[1];
        }
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comp());
        List<Integer> list = new ArrayList<>();
        for (int i = 0 ; i < nums.length ; i++) {
            queue.offer(new int[]{i, nums[i]});
            if (i < k-1) {
                continue;
            }
            while(!queue.isEmpty() && (i-queue.peek()[0]) >= k) {
                queue.poll();
            }
            int localmax = queue.peek()[1];
            list.add(localmax);
        }
        int[] ret = new int[list.size()];
        for (int i = 0 ; i < list.size() ; i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }

  • 1
    C

    @ObjectNotFound You can define a maxHeap simply as:

    Queue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());

Log in to reply
 

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