剑指offer 64.滑动窗口的最大值 & leetcode 剑指 Offer 59

64.滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

思路一：

双重循环，算法复杂度为O(nk), k 为窗口大小

 1 class Solution {
 2     public int[] maxSlidingWindow(int[] nums, int k) {
 3         if(nums == null || nums.length == 0){
 4             return new int[0];
 5         }
 6         // 双重循环，暴力，算法复杂度为O(nk)
 7         int len = nums.length;
 8         int size = len > k ? len - k + 1 : 1;   // 求出结果数组的大小
 9         int[] res = new int[size];
10 
11         // 双重循环
12         for(int i = 0; i < size; i++){
13             int max = nums[i];
14             for(int j = i; j < k+i && j < len; j++){
15                 max = Math.max(max, nums[j]);
16             }
17             res[i] = max;
18         }
19         return res;
20         
21     }
22 }

leetcode运行时间为35 ms - 16.88%，空间为46.7 MB - 74.15%

复杂度分析：

时间复杂度：经过双重for循环，时间复杂度为O(n)

空间复杂度：除了一个结果数组外不需要其他额外的空间，所以空间复杂度为O(1)

思路二：

思路一的改进版，再仔细想，是不是有必要每次移动窗口就把窗口内所有元素都遍历一遍来重新统计最大值呢，如果经过窗口移动后，最大值仍在窗口内，或者说最大值是此次窗口获取到的新元素，那是不是就不用就把窗口内所有元素都遍历一遍来重新统计最大值了呢，所以经过改进后的程序为：

仍然是双重for循环，但是如果此次窗口移动丢弃的元素并不是窗口的最大值，那我们就只需要把上次窗口最大值和此次移动增加的新值比较，更新最大值即可，如果此次窗口移动丢弃的元素确实是是窗口的最大值，还是需要遍历窗口的所有元素

 1 class Solution {
 2     public int[] maxSlidingWindow(int[] nums, int k) {
 3         if(nums == null || nums.length == 0){
 4             return new int[0];
 5         }
 6         // 双重循环，暴力，算法复杂度为O(nk)
 7         int len = nums.length;
 8         int size = len > k ? len - k + 1 : 1;   // 求出结果数组的大小
 9         int[] res = new int[size];
10 
11         int max = -1 << 30;
12         // 双重循环
13         for(int i = 0; i < size; i++){
14 
15             // 如果丢弃的元素并不是上次窗口的最大值,
16             // 只需要把上次窗口最大值和此次移动增加的新值比较，更新最大值即可
17             if(i != 0 && res[i-1] != nums[i-1]){
18                 res[i] = Math.max(res[i-1], nums[i+k-1]);
19             }else{
20                 max = nums[i];
21                 for(int j = i; j < k+i && j < len; j++){
22                     max = Math.max(max, nums[j]);
23                 }
24                 res[i] = max;
25             }
26         }
27         return res;
28     }
29 }

leetcode 运行时间为3ms - 92.66%, 空间为47MB - 58.67%, 可以看到，运行时间比刚才短了很多

复杂度分析：

时间复杂度：同样是双重for循环，但是经过了优化处理，复杂度其实是降低了的，每个窗口最大值进入窗口和出窗口各一次，所以复杂度为O(n), k越大，效率提升越明显

空间复杂度：除了一个结果数组外不需要其他额外的空间，所以空间复杂度为O(1)

思路三：

思路参考：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/mian-shi-ti-59-i-hua-dong-chuang-kou-de-zui-da-1-6/

借用剑指 Offer 59 - II. 队列的最大值的方法，维护一个存储了最大值的递减单调队列，队首元素始终就是新窗口的最大值。

如果队列不为空且队列的对首元素等于上一次滑出窗口的元素，就应该将这个队首元素出队。然后将窗口新加入的元素入队，不过入队之前要先把队尾小于该元素的所有元素删除。当元素下标大于nums[]长度或者 k 时，需要保存一个窗口最大值到结果数组

 1 class Solution {
 2     public int[] maxSlidingWindow(int[] nums, int k) {
 3         if(nums == null || nums.length == 0){
 4             return new int[0];
 5         }
 6         // 双重循环，暴力，算法复杂度为O(nk)
 7         int len = nums.length;
 8         int size = len > k ? len - k + 1 : 1;   // 求出结果数组的大小
 9         int[] res = new int[size];
10 
11         int max = -1 << 30;
12         Deque<Integer> deque = new LinkedList<Integer>();
13         // 如果队列不为空且队列的对首元素等于上一次滑出窗口的元素，就应该将这个队首元素出队。
14         // 然后将窗口新加入的元素入队，不过入队之前要先把队尾小于该元素的所有元素删除。
15         // 当元素下标大于nums[]长度或者 k 时，需要保存一个窗口最大值到结果数组
16         int j = 0;
17         for(int i = 0; i < nums.length; i++){
18             if(i >= k && nums[i-k] == deque.peekFirst()){
19                 deque.pollFirst();
20             }
21             while(!deque.isEmpty() && nums[i] > deque.peekLast()){
22                 deque.pollLast();
23             }
24             deque.offerLast(nums[i]);
25 
26             if(i >= nums.length - 1 || i >= k - 1){
27                 res[j++] = deque.peekFirst();
28             }
29         }
30         return res;
31     }
32 }

leetcode运行时间为：15ms - 54.71%, 空间为47.6 MB - 28.03%

复杂度分析：

时间复杂度：很容易看出来，整个程序只对数组进行了一次遍历，所以时间复杂度为O(n), 但是因为这个涉及到deque 的操作，所以时间上会比思路二直接操作数组慢一些

空间复杂度：除了一个结果数组，还借助了一个双端队列，队列的大小最多为O(k), 所以空间复杂度为O(k)