Simple java O(n) solution


  • 0
    S
    public class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums.length==0) return new int[0];
            LinkedList<Integer> dq = new LinkedList<Integer>();
            int[] res = new int[nums.length - k + 1];
            int index = 0;
            for(int i=0;i<nums.length;i++){
                index = i-k+1;
                if(dq.size()==0) dq.offer(i);
                while(dq.size()!=0 && nums[dq.peekLast()]<=nums[i]) dq.pollLast();
                dq.offer(i);
                while(dq.size()!=0 && dq.peekFirst()<=i-k) dq.pollFirst();
                if(index>=0) res[index] = nums[dq.peek()];
            }
            return res;
        }
    }
    

  • 0
    Z

    I am confused by the solution, when you do the comparison, the worst case you still have to go through k elements. How come it is not O(kn)? In addition, I don't know if it is significantly different from a "max" heap implementation, while that is of O(nlogn)


Log in to reply
 

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