Java not linear solution O(kn), but beats 98.4%


  • 0
    K

    Do not satisfy the requirement. Just sharing my first instinct implementation with this question.

    If the array is very large and descending, running time would be worst case of O(k*n). This solution would be slower than queue method.

    
    //  using two point method, and keep records of maxVal and maxIndex
    
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
    
            if (nums == null || nums.length == 0) {
                return new int[]{};
            }
    
            int[] res = new int[nums.length - k + 1];
            int maxIndex = 0;
            int maxVal = Integer.MIN_VALUE;
    
            //  start is start index
            for (int start = 0, end = 0, resIndex = 0; end < nums.length; end++) {
    
                //  last maxVal is forgotten
                if (start > maxIndex) {
                    maxVal = Integer.MIN_VALUE;
                    end = start;
                }
    
                //  update maxVal and maxIndex
                if (nums[end] > maxVal) {
                    maxIndex = end;
                    maxVal = nums[end];
                }
    
                //  if end reaches last index of sliding window, then add maxVal to res and increment startIndex
                if (end - start == k - 1) {
                    res[resIndex++] = maxVal;
                    start++;
                }
            }
    
            return res;
        }
    }
    

Log in to reply
 

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