beat 98% Only simple scan array, no additional data structure


  • 0
    F

    // it is easy to solve this problem by scanning every element twice.

        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums.length == 0) return new int[0];
            int[] res = new int[nums.length-k+1];
            int leftIndex = 0;
            int kcount = 0;
            int resIndex = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[leftIndex] <= nums[i]) leftIndex = i;
                kcount++;
                if (kcount == k) {
                    res[resIndex++] = nums[leftIndex];
                    kcount--;
                    if (leftIndex == i-k+1) {
                        leftIndex = i-k+2;
                        for (int j = i-k+2; j <= i; j++) {
                            if (nums[leftIndex] <= nums[j]) leftIndex = j;
                        }
                    }
                }
            }
            
            return res;
        }

Log in to reply
 

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