Java O(n) solution using LinkedList


  • 0
    C
        public int[] maxSlidingWindow(int[] nums, int k) {
            int  []results = new int[nums.length - k + 1];
            int j = 0;
            LinkedList<Integer> queue = new LinkedList<>();
            if (nums == null || nums.length == 0){
                int []res = new int[0];
                return res;
            }
            if (k == 1){
                for (int i : nums){
                    results[j++] = i;
                }
                return results;
            }
            queue.add(0);
            for (int i = 1; i < nums.length; i++){
                if (i >= k){
                    int index = queue.getFirst();
                    results[j++] = nums[index];
                    while (i - queue.getFirst() >= k){
                        queue.removeFirst();
                    }
                }
                while (!queue.isEmpty() && 
                    nums[queue.getLast()] < nums[i]){
                    queue.removeLast();
                }
                queue.add(i);
            }
            results[j] = nums[queue.getFirst()];
            return results;
        }
    }
    but there still exists one problem WHEN k == 1 I have to write A new loop to cope with the situation hope anyone can help me figure out the problem...I am just a greener 
    THANKS!!!!

Log in to reply
 

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