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

（本题出现于快手2020校园招聘秋招笔试算法C试卷）

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

解释:
    滑动窗口的位置          最大值
[1  3  -1]  -3  5  3  6  7       3
1  [3  -1  -3]  5  3  6  7       3
1  3  [-1  -3  5]  3  6  7       5
1  3  -1  [-3  5  3]  6  7       5
1  3  -1  -3  [5  3  6]  7       6
1  3  -1  -3  5  [3  6  7]       7

题目分析：

思路一：最笨的方法，使用暴力。两层循环，外循环（变量 i 控制）遍历数组的前 （nums.length-k+1） 个元素。并将最大值初始化为外循环的第一个元素。内循环（变量 j 控制）遍历 （k-1） 次，将外循环设置的最大值与num[i+j+1] 比较，如果当前的最大值更小，则将num[i+j+1] 赋值给最大值。

时间复杂度是 O ( k N ) O(kN) O(kN)，其中 k k k 是滑动窗口的长度。空间复杂度是 O ( N − k + 1 ) O(N - k + 1) O(N−k+1)，用于输出数组。

边界条件：

1. 数组没有元素，数组为空，k值大于数组长度。
if (nums.length<k||nums==null||nums.length==0){
	return new int[0];
}

Java代码：

import java.util.Arrays;
/**
 * 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
 * 示例:
 * 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
 * 输出: [3,3,5,5,6,7]
 * 解释:
 *
 * 滑动窗口的位置                最大值
 * [1  3  -1] -3  5  3  6  7       3
 *  1 [3  -1  -3] 5  3  6  7       3
 *  1  3 [-1  -3  5] 3  6  7       5
 *  1  3  -1 [-3  5  3] 6  7       5
 *  1  3  -1  -3 [5  3  6] 7       6
 *  1  3  -1  -3  5 [3  6  7]      7
 */

public class Offer59_I {
    public static  int[] maxSlidingWindow(int[] nums, int k) {
        // 边界条件判断
        if (nums.length==0||nums.length<k||nums==null){
            return new int[0];
        }
        int end = nums.length-k;
        int[] result = new int[end+1];
        for (int i = 0; i <= end; i++) {
            int max = nums[i];
            for (int j = 1; j < k; j++) {
                if (nums[i+j]>max){
                    max=nums[i+j];
                }
            }
            result[i] = max;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] array = {1,3,-1,-3,5,3,6,7};
        System.out.println(Arrays.toString(maxSlidingWindow(array,3)));
    }
}

思路二：这道题不复杂，难点在于如何在 O ( 1 ) O(1) O(1)时间复杂度算出每个「窗口」中的最大值，使得整个算法在线性时间完成。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0){
            return new int[0];
        }
        Deque<Integer> d = new LinkedList<Integer>();
        int res[] = new int[nums.length - k +1];
        for(int j = 0,i = 1-k;j<nums.length;i++,j++){
            if(i> 0 && d.peekFirst() == nums[i-1] ){
                d.pollFirst();//若i>0 且队首元素deque[0] = 被删除元素nums[i-1] ，则队首元素出队
            }
            while(!d.isEmpty()&&d.peekLast()<nums[j]){
                d.pollLast();//删除deque内所有小于nums[j]的元素
            }
             d.addLast(nums[j]);//将nums[j]添加至deque尾部
            if(i >= 0){
                res[i] = d.peekFirst();//若已形成窗口（i>=0)，将窗口最大值（即队首元素deque[0]）添加至res
            }         
        }
        return res;
    }
}

【注】
（1）：leetcode 等平台只要我们完成一个函数即可，本人初出茅庐，为了巩固基本知识，故自己补充了部分代码，用于练手。本代码也许存在漏洞，望高手赐教。感谢！