Java 4 ms solution, beats 97.66%


  • 0

    This solution is O(n^2) in the worst case when we have a decreasing array but quite fast in the average case. The idea is keep tracking the index of local maximum. Any thought or opinion is appreciated.

    class Solution {
        int maxIndex;
        int maxValue;
        public int[] maxSlidingWindow(int[] nums, int k) {
            int[] result = new int[nums.length-k+1];
            if(nums.length == 0 || k < 1 || k > nums.length)
                return new int[0];
            
            for(int i = 0; i+k-1 < nums.length; i++){
                if(i == 0 || i > maxIndex){
                    findMax(nums,i,i+k);
                }
                else if(nums[i+k-1] >= maxValue){
                    maxIndex = i+k-1;
                    maxValue = nums[i+k-1];
                }
                
                result[i] = maxValue;
            }
            return result;
        }
        
        void findMax(int[] nums, int start, int end){
            maxIndex = start;
            maxValue = nums[start];
            for(int i = start; i < end; i++){
                if(nums[i] >= maxValue){
                    maxValue = nums[i];
                    maxIndex = i;
                }
                    
            }
        }
    }
    

Log in to reply
 

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