|
| 1 | +##题目地址 |
| 2 | + |
| 3 | +https://leetcode.com/problems/sliding-window-maximum/description/ |
| 4 | + |
| 5 | +##题目描述 |
| 6 | + |
| 7 | +``` |
| 8 | +Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. |
| 9 | +
|
| 10 | +Example: |
| 11 | +
|
| 12 | +Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3 |
| 13 | +Output: [3,3,5,5,6,7] |
| 14 | +Explanation: |
| 15 | +
|
| 16 | +Window position Max |
| 17 | +--------------- ----- |
| 18 | +[1 3 -1] -3 5 3 6 7 3 |
| 19 | + 1 [3 -1 -3] 5 3 6 7 3 |
| 20 | + 1 3 [-1 -3 5] 3 6 7 5 |
| 21 | + 1 3 -1 [-3 5 3] 6 7 5 |
| 22 | + 1 3 -1 -3 [5 3 6] 7 6 |
| 23 | + 1 3 -1 -3 5 [3 6 7] 7 |
| 24 | +Note: |
| 25 | +You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array. |
| 26 | +
|
| 27 | +Follow up: |
| 28 | +Could you solve it in linear time? |
| 29 | +``` |
| 30 | + |
| 31 | +##思路 |
| 32 | + |
| 33 | +符合直觉的想法是直接遍历 nums, 然后然后用一个变量 slideWindow 去承载 k 个元素， |
| 34 | +然后对 slideWindow 求最大值，这是可以的，时间复杂度是 O(n\* k).代码如下： |
| 35 | + |
| 36 | +```js |
| 37 | +/** |
| 38 | + *@param{number[]}nums |
| 39 | + *@param{number}k |
| 40 | + *@return{number[]} |
| 41 | +*/ |
| 42 | +varmaxSlidingWindow=function(nums,k) { |
| 43 | +// bad 时间复杂度O(n * k) |
| 44 | +if (nums.length===0|| k===0)return []; |
| 45 | +let slideWindow= []; |
| 46 | +constret= []; |
| 47 | +for (let i=0; i<nums.length- k+1; i++) { |
| 48 | +for (let j=0; j< k; j++) { |
| 49 | +slideWindow.push(nums[i+ j]); |
| 50 | + } |
| 51 | +ret.push(Math.max(...slideWindow)); |
| 52 | + slideWindow= []; |
| 53 | + } |
| 54 | +return ret; |
| 55 | +}; |
| 56 | +``` |
| 57 | + |
| 58 | +但是如果真的是这样，这道题也不会是 hard 吧？这道题有一个 follow up，要求你用线性的时间去完成。 |
| 59 | +我们可以用双端队列来完成，思路是用一个双端队列来保存`接下来的滑动窗口可能成为最大值的数`。具体做法： |
| 60 | + |
| 61 | + |
| 62 | +- 入队列 |
| 63 | + |
| 64 | +- 移除失效元素，失效元素有两种 |
| 65 | + |
| 66 | +1. 一种是已经超出窗口范围了，比如我遍历到第4个元素，k = 3，那么i = 0的元素就不应该出现在双端队列中了 |
| 67 | +具体就是`索引大于 i - k + 1的元素都应该被清除` |
| 68 | + |
| 69 | +2. 小于当前元素都没有利用价值了，具体就是`从后往前遍历（双端队列是一个递减队列）双端队列，如果小于当前元素就出队列` |
| 70 | + |
| 71 | + |
| 72 | +如果你仔细观察的话，发现双端队列其实是一个递减的一个队列。因此队首的元素一定是最大的。用图来表示就是： |
| 73 | + |
| 74 | + |
| 75 | + |
| 76 | +##关键点解析 |
| 77 | + |
| 78 | +- 递归简化操作 |
| 79 | +- 如果树很高，建议使用栈来代替递归 |
| 80 | +- 这道题目对顺序没要求的，因此队列数组操作都是一样的，无任何区别 |
| 81 | + |
| 82 | +##代码 |
| 83 | + |
| 84 | +```js |
| 85 | +/* |
| 86 | + * @lc app=leetcode id=239 lang=javascript |
| 87 | + * |
| 88 | + * [239] Sliding Window Maximum |
| 89 | + * |
| 90 | + * https://leetcode.com/problems/sliding-window-maximum/description/ |
| 91 | + * |
| 92 | + * algorithms |
| 93 | + * Hard (37.22%) |
| 94 | + * Total Accepted: 150.8K |
| 95 | + * Total Submissions: 399.5K |
| 96 | + * Testcase Example: '[1,3,-1,-3,5,3,6,7]\n3' |
| 97 | + * |
| 98 | + * Given an array nums, there is a sliding window of size k which is moving |
| 99 | + * from the very left of the array to the very right. You can only see the k |
| 100 | + * numbers in the window. Each time the sliding window moves right by one |
| 101 | + * position. Return the max sliding window. |
| 102 | + * |
| 103 | + * Example: |
| 104 | + * |
| 105 | + * |
| 106 | + * Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3 |
| 107 | + * Output: [3,3,5,5,6,7] |
| 108 | + * Explanation: |
| 109 | + * |
| 110 | + * Window position Max |
| 111 | + * --------------- ----- |
| 112 | + * [1 3 -1] -3 5 3 6 7 3 |
| 113 | + * 1 [3 -1 -3] 5 3 6 7 3 |
| 114 | + * 1 3 [-1 -3 5] 3 6 7 5 |
| 115 | + * 1 3 -1 [-3 5 3] 6 7 5 |
| 116 | + * 1 3 -1 -3 [5 3 6] 7 6 |
| 117 | + * 1 3 -1 -3 5 [3 6 7] 7 |
| 118 | + * |
| 119 | + * |
| 120 | + * Note: |
| 121 | + * You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty |
| 122 | + * array. |
| 123 | + * |
| 124 | + * Follow up: |
| 125 | + * Could you solve it in linear time? |
| 126 | +*/ |
| 127 | +/** |
| 128 | + *@param{number[]}nums |
| 129 | + *@param{number}k |
| 130 | + *@return{number[]} |
| 131 | +*/ |
| 132 | +varmaxSlidingWindow=function(nums,k) { |
| 133 | +// 双端队列优化时间复杂度, 时间复杂度O(n) |
| 134 | +constdeque= [];// 存放在接下来的滑动窗口可能成为最大值的数 |
| 135 | +constret= []; |
| 136 | +for (let i=0; i<nums.length; i++) { |
| 137 | +// 清空失效元素 |
| 138 | +while (deque[0]< i- k+1) { |
| 139 | +deque.shift(); |
| 140 | + } |
| 141 | + |
| 142 | +while (nums[deque[deque.length-1]]< nums[i]) { |
| 143 | +deque.pop(); |
| 144 | + } |
| 145 | + |
| 146 | +deque.push(i); |
| 147 | + |
| 148 | +if (i>= k-1) { |
| 149 | +ret.push(nums[deque[0]]); |
| 150 | + } |
| 151 | + } |
| 152 | +return ret; |
| 153 | +}; |
| 154 | +``` |
| 155 | + |
| 156 | +##扩展 |
| 157 | + |
| 158 | +###为什么用双端队列 |
| 159 | +因为删除无效元素的时候，会清除队首的元素（索引太小了 |
| 160 | +）或者队尾(元素太小了)的元素。 因此需要同时对队首和队尾进行操作，使用双端队列是一种合乎情理的做法。 |
