【Java题解】剑指 Offer 59 - I. 滑动窗口的最大值

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

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

方法一：
暴力。

1. 定义一个长度为滑动窗口可滑动长度的数组，用来记录每一个窗口中的最大值。

代码：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if (len == 0 || k == 0) return new int[0];
        if (k == 1) return nums;
        int l = 0, r = l + k - 1;
        int[] res = new int[len - k + 1];
        int idx = 0;
        if (len < k) return new int[findMax(l, r, nums)];
        else {
            while (r < len) {
                res[idx++] = findMax(l, r, nums);
                l++;
                r++;
            }
        }
        return res;
    }

    private int findMax(int l, int r, int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int i = l; i <= r; i++) {
            max = Math.max(max, nums[i]);
        }
        return max;
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

更好的方法待续…