My java code beat 97%


  • 0
    Y

    The optimum case: the list is sorted in ascending order, it gives O(n) time. The worst case: the list is in descending order, it gives O(nk).

    public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0){
            return new int[0];
        }
        
        int max = Integer.MIN_VALUE;
        int maxIndex = -1;
        int [] ret = new int[nums.length - k + 1];
        
        for(int i = 0; i < k; i ++){
            if(max < nums[i]){
                max = nums[i];
                maxIndex = -1;
            }
        }
        ret[0] = max;
        for(int i = 1; i < nums.length - k + 1; i ++){
            if(max < nums[i + k - 1]){
                max = nums[i + k - 1];
                maxIndex = i + k - 1;
            }
            if(maxIndex < i){
                max = Integer.MIN_VALUE;
                maxIndex = -1;
                for(int j = 0; j < k; j ++){
                    if(max < nums[i + j]){
                        max = nums[i + j];
                        maxIndex = i + j;
                    }
                }
            }
            ret[i] = max;
        }
        
        return ret;
    }
    }

Log in to reply
 

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