Java O(n) no deque


  • 0
    A

    Keep a max index to indicate not to compare again elements index < max index.

    public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums.length == 0 || k == 0) {
                return new int[0];
            }
            
            int[] results = new int[nums.length - k + 1];
            int curMaxInd = -1;
            
            for (int i=0; i<=nums.length-k; i++) {
                int start = i;
                int end = i+k-1;
                
                if (curMaxInd >= start && curMaxInd <= end) {
                    //compare with the new element with index end if prev max within current range, 
                    //if new element is larger, update the index
                    if (nums[end] > nums[curMaxInd]) {
                        curMaxInd = end;
                    }
                    results[i] = nums[curMaxInd];       
                } else {
                    //recalculate and update the maxInd
                    int max = 0;
                    curMaxInd = start;
                    for (int j=start; j<=end; j++) {
                        if (nums[j] > max) {
                            max = nums[j];
                            curMaxInd = j;
                        }
                    }
                    results[i] = nums[curMaxInd];
                }
            }
            return results;
        }```

Log in to reply
 

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