Easy understand Java O(N) in time and O(1) in space 4ms beats 97% with explanation


  • 0
    T

    So for the first k elements, we calculate its max then assign to res[0] which res is an int array for return
    Then we update when next element comes. If current max still in the interval, just compare to the new element, else we need to find new max in new interval. The worst case is descending order which is O(nk), n is the length of arr. Still can be considered as O(n) if k is a constant.

    public int[] maxSlidingWindow(int[] arr, int k) {
        
        if(arr.length==0 || k==1) return arr;
              
        int len=arr.length-k+1, i=0, max=arr[0];
        // an int array for return 
        int[] res = new int[len];
        // Find max from the first k elements
        for (i=0; i<k; i++) {
            max = Math.max(arr[i], max);
        }
        // Assign to res[0]
        res[0] = max;
        
        for (i=1; i<len; i++) {
            // After add and remove new element, If max is no longer in current round, find it again like first round.
            if (arr[i-1] == max) {
                max = arr[i];
                
                for (int j=i; j<=i+k-1; j++) {
                    max = Math.max(arr[j], max);
                }
            }
            // max still in current round, then compare to new added element only
            else {
                max = Math.max(max, arr[i+k-1]);
            }
            res[i] = max;
        }
        return res;
    }

Log in to reply
 

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