LeetCode(76) -- 239

P239. Sliding Window Maximum (Hard)

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

My Solution

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if (len == 0) {
            return new int[0];
        }
        int[] ans = new int[len - k + 1];
        int max = Integer.MIN_VALUE;
        int maxIndex = 0;
        for (int i = 0; i < k; i++) {
            if (nums[i] > max) {
                max = nums[i];
                maxIndex = i;
            }
        }
        ans[0] = max;
        for (int i = 1; i < ans.length; i++) {
            int newValue = nums[i + k - 1];
            if (newValue >= max) {
                max = newValue;
                ans[i] = newValue;
                maxIndex = i + k - 1;
            } else if (maxIndex < i) {
                max = Integer.MIN_VALUE;
                for (int j = i; j < i + k; j++) {
                    if (nums[j] > max) {
                        max = nums[j];
                        maxIndex = j;
                    }
                }
                ans[i] = max;
            } else {
                ans[i] = max;
            }
        }
        return ans;
    }
}

100%

The Best Solution

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) return new int[0];       
        int[] res = new int[nums.length - k + 1];        
        int windowMaxIdx = 0;
        for (int i = 0; i < k; i++) {
            if (nums[i] >= nums[windowMaxIdx]) {
                windowMaxIdx = i;
            }//现在window没移动前 求出当前的max的index 然后输出值到res的第一位
        }
        res[0] = nums[windowMaxIdx];       
        for (int right = k; right < nums.length; right++) { //right是wind内最右侧的index
            int left = right - k + 1; //从1开始
            if (nums[right] >= nums[windowMaxIdx]) windowMaxIdx = right;
            else if (windowMaxIdx <left ) 
            { //这里是之前的window最大index不再在win里了
                windowMaxIdx=left; //需要暂时将最左看成max
                for(int i= left+1; i<=right;i++)
                {            
                    if (nums[i] >= nums[windowMaxIdx]) windowMaxIdx = i;  //在window中找更大的
                }                
            }
            res[left] = nums[windowMaxIdx];//输出给res
        }
        
        return res;
    }
}

跟我思路一样，不用学了。