Java solution, beat 92%


  • 0
    D

    '''

    public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
    if(nums == null || nums.length == 0)
    return new int[0];

        int i = 0;
        int len = nums.length;
        int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        
        LinkedList<Integer> queue = new LinkedList<Integer>();
        int[] res = new int[nums.length - k + 1];
        
        for(; i < k; i++)
            queue.offerFirst(nums[i]);
        
        int mark = 0;
        for(int j = 0; j < k; j++){
            if(nums[j] >= max1){
                max1 = nums[j];
                mark = j;
            }
        }
        if(mark != k - 1){
            max2 = nums[mark + 1];
            for(int j = mark + 2; j < k; j++)
                max2 = Math.max(max2, nums[j]);
        }
        
        res[i - k] = max1;
        
        while(queue.peekLast() != max1)
            queue.pollLast();
        
        for(; i < len; i++){
            if(nums[i] >= max1){
                queue.clear();
                queue.offerFirst(nums[i]);
                max2 = Integer.MIN_VALUE;
                max1 = nums[i];
            }
            else{
                if(queue.size() < k){
                    queue.offerFirst(nums[i]);
                    max2 = Math.max(max2, nums[i]);
                }
                else{
                    queue.offerFirst(nums[i]);
                    
                    max1 = Math.max(max2, nums[i]);
                    while(queue.peekLast() != max1)
                        queue.pollLast();
                    
                    if(queue.size() == 1)
                        max2 = Integer.MIN_VALUE;
                    else{
    
                        max2 = queue.get(queue.size() - 2);
                        for(int m = queue.size() - 3; m >= 0; m--)
                            max2 = Math.max(max2, queue.get(m));
    
                    }
                        
                }
            }
            
            res[i - k + 1] = max1;
        }
        
        
        return res;
    }
    

    }
    '''


Log in to reply
 

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