My java solution


  • 0
    L

    I use a priority queue to mem the window ,as the window moves ,the priority queue changes,
    the time of insert and removal of numbers in this queue is O(lgK),so the total time is O(n*lgk)

    public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(k==0){
            return new int[0];
        }
    	 Comparator<Integer> OrderIsdn =  new Comparator<Integer>(){  
                public int compare(Integer o1, Integer o2) {  
                    if(o1-o2>0) return -1;
                    if(o1-o2<0) return 1;
                    return 0;
                }  
    	 };
    	 int[] l = new int[nums.length-k+1];
    	 int j = 0;
         PriorityQueue<Integer> q = new PriorityQueue<Integer>(nums.length,OrderIsdn);
         int start = 0;
         for (int i = 0; i <= k-1; i++) {
    		q.add(nums[i]);
    	}
         l[j++] = q.peek();
         for(int i = k;i<=nums.length-1;i++){
        	 q.remove(new Integer(nums[start++]));
        	 q.add(nums[i]);
        	 l[j++] = q.peek();
         }
    	 return l;
            }
        }

Log in to reply
 

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