题目大意：
滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 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
提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
进阶：
你能在线性时间复杂度内解决此题吗？
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=239
解题思路分析：
本题是一道高频面试题，这里介绍二种解题思路。时间复杂度分别是O(nlogn)以及O(n)
解法一：二分查找，时间复杂度 O(nlogn)
按顺序遍历一遍数组，循环时，将当前元素插入到一个新建List集合中，插入时采用二分查找方式插入，以保证List内数字是有小到大排序。当循环下标移动到数组的k-1位置时，也就是List的大小等于k时，说明当前区间长度已经满足k，我们需要在当前区间找到一个最大值加入返回结果，由于List已经排好序，因此当前区间内的最大值应该是List中的最后一个元素。继续循环到数组的下一位，此时下标k-i位上的数字将会被移除出k区间，我们应该从List中删除数组中对应的k-i位上的数字，然后再使用二分查找方式将第i位的数字插入到List中，以此类推，直到循环完数组中所有数字。
本解法循环数组的时间复杂度是数组长度n，每次向List中插入数据的时间花费logn，因此总的时间复杂度为 O(nlogn) 。
实现代码：
public int[] maxSlidingWindow(int[] nums, int k) {
// 如果数组为空，直接返回空
if(nums.length==0) return new int[0];
// 排序用的List
List<Integer> list = new ArrayList<>();
// 返回结果
int[] res = new int[nums.length-k+1];
// 循环数组中每一个数字
for(int i=0;i<nums.length;i++){
// 如果List的大小等于k，说明当前元素插入之前k区间内的元素已满，
// 需要删除区间最左边的元素，即下标为i-k位的数字
if(list.size()==k){
list.remove(Integer.valueOf(nums[i-k]));
}
// 当前进入k区间的元素
int in = nums[i];
// 利用二分查找，找到当前元素插入位置，保证list升序
int left=0, right=list.size()-1;
while(left<=right){
int mid=(left+right)/2;
int midNum=list.get(mid);
if(in==midNum){
left=mid;
break;
}
if(in>midNum) left=mid+1;
else right=mid-1;
}
// 将当前元素插入到list中
list.add(left, in);
// 如果当前区间长度等于k，找到一个最大值存入返回结果
if(list.size()==k) res[i-k+1]=list.get(k-1);
}
return res;
} 本解法执行时间为32ms。
Runtime: 32 ms, faster than 26.92% of Java online submissions for Sliding Window Maximum.
Memory Usage: 41.3 MB, less than 81.25% of Java online submissions for Sliding Window Maximum.
解法二：Deque，时间复杂度为O(n)
之前的文章并没有涉及过Deque的讲解，这里重点分享一下，Deque解法也是本题官方给出的最优解法，面试时使用这种解法也会令你的面试官对你刮目相看。
之前的文章多次讲过堆栈Queue，它是广度优先搜索bfs算法的核心。堆栈Queue是基于先进先出的原则，而且是单向的，也就是说，我们只能向队伍的尾部插入数据，然后从头部取出数据，类似于人群排队。而Deque也是一种Queue，被称为双向堆栈，我们不仅可以向队尾插入数据，也允许向头部添加数据，同理取数据时，头尾两侧的数据均可以取出。
回到本题，通过题目中给出的提示信息来分析，在Deque中仅存储有价值的数据，没用的全部移除掉。那么我们需要考虑什么数据是没用的？举个例子来说明一下，还是使用题目中的例子：
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
我们还是需要按顺序循环一遍数组元素，先将1放入到 Deque 的尾部，此时 Deque 中只有数字1。接下来需要将3放入堆栈尾部，在放入之前，先从 Deque 尾部向前查看已存在的数字，数字1要小于当前的3，我们可以认定数字1就是没用的那个元素！原因分析：因为当前3大于1，在向右滑动k区间的过程中，当3被移除出区间之前，1永远不会是最大的那个值，并且在3被移除出区间的时间点，数字1已经先一步被移除出区间了，因此无论如何1也不会被选作最大值，即1是无用数据。以此类推，在插入当前数字之前，Deque中所有小于当前数字的元素都是可以被删除掉的，删除这些无用数据之后，再插入当前数字即可，此时 Deque 中的数据能够保证由大到小的顺序排列（头最大，尾最小）。由此可得出区间内的最大值一定是 Deque 的头元素。
解题时，还需要注意另外一个问题，区间是有长度限制的，即题目给出的k值。在区间向右滑动的过程中，不仅要将区间右下标的值加入到区间内，还需要将区间左下标减一的值移除出区间，当Deque的头元素等于 区间左下标减一对应的数字 时，Deque的头元素需要被移除掉。
实现代码：
public int[] maxSlidingWindow(int[] nums, int k) {
// 如果数组为空，直接返回空
if(nums.length==0) return new int[0];
// 返回结果
int[] res = new int[nums.length-k+1];
// 保存区间内数字用的Deque
Deque<Integer> dq = new LinkedList<>();
// 循环数组中每个数字
for(int i=0;i<nums.length;i++){
// 当前数字
int num = nums[i];
// 如果Deque元素个数大于0并且头元素等于k区间左下标减一的数
if(dq.size()>0&&i-k>=0&&dq.peekFirst()==nums[i-k]){
// 移除头元素
dq.pollFirst();
}
// 移除无用元素
while(dq.size()>0 && dq.peekLast()<num){
dq.pollLast();
}
// 添加当前元素
dq.offerLast(num);
// 当前为合理区间
if(i>=k-1){
// 将区间内最大值加入到返回结果
res[i-k+1]=dq.peekFirst();
}
}
return res;
} 本解法执行时间为10ms。
Runtime: 10 ms, faster than 77.52% of Java online submissions for Sliding Window Maximum.
Memory Usage: 41.3 MB, less than 82.81% of Java online submissions for Sliding Window Maximum.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-239-sliding-window-maximum-解题思路分析/
View Comments (0)