题目

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

思考

一开始用一个新数组来存储窗口，每次窗口更新都要进行判断大小，后面看题解，需要改变值的范围确定窗口就行，不需要新的数组来存储，用一个变量计录窗口的最大值，窗口更新时与最大值比较，如果更大就更换最大值，用一个变量记录最大值下标，如果最大值不在窗口内就在窗口内进行循环找出最大值

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0)
            return new int[0];
        int[] a = new int[k];
        int[] x = new int[nums.length - k + 1];
        int flag = 0;
        int count = 0;
        for (int i = 0; i <= nums.length; i++) {
            if (i < k) {
                a[i] = nums[i];
            } else {
                if (i == nums.length) {
                    x[count] = maxNumbers(a, k);
                    a[flag] = nums[i - 1];
                    count++;
                    flag++;
                } else {
                    x[count] = maxNumbers(a, k);
                    a[flag] = nums[i];
                    count++;
                    flag++;
                }
            }
            if (flag > k - 1)
                flag = 0;
        }
        return x;
    }

    public int maxNumbers(int[] nums, int k) {
        int max = nums[0];
        for (int i = 1; i < k; i++) {
            if (nums[i] > max)
                max = nums[i];
        }
        return max;
    }
}


改良后
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0)
            return new int[0];
        int[] x = new int[nums.length - k + 1];
        int max = 0, maxInd = -1;
        for (int i = 0; i < nums.length - k + 1; i++){
            if (maxInd >= i){
                if (nums[i + k - 1] > max){
                    max = nums[i + k - 1];
                    maxInd = i + k - 1;
                }
            } else {
                max = nums[i];
                for (int n = i; n < i + k; n++){
                    if (max < nums[n]){
                        max = nums[n];
                        maxInd = n;
                    }
                }
            }
            x[i] = max;
        }
        return x;
    }
}