leetcode239：滑动窗口最大值问题 #33
Comments
|
|
|
var maxSlidingWindow = function(nums, k) { |
|
|
nums.slice(0, 1 - k).map((v, index) => Math.max(...nums.slice(index, index + k))); |
|
var ss = function(num,k) { } |
function slideWindow(arr, k) {
let i = 0
let ret = []
while(i <= arr.length - k) {
let max = Math.max.apply(Math, arr.slice(i, i + k))
ret.push(max)
i++
}
return ret
} |
解答一：暴力解法const maxSlidingWindow = function(nums, k) {
if(k === 1) return nums
let result = [], arr = []
for(let i = 0; i < nums.length; i++) {
arr.push(nums[i])
if(i >= k-1) {
result.push(Math.max(...arr))
arr.shift()
}
}
return result
};复杂度分析： 时间复杂度：O(n*k) 空间复杂度：O(n) 解答二：优化：双端队列解题思路： 使用一个双端队列存储窗口中值的 索引 ，并且保证双端队列中第一个元素永远是最大值，那么只需要遍历一次
代码实现： const maxSlidingWindow = function (nums, k) {
const deque = []
const result = []
for (let i = 0; i < nums.length; i++) {
// 把滑动窗口之外的踢出
if (i - deque[0] >= k) {
deque.shift()
}
while (nums[deque[deque.length - 1]] <= nums[i]) {
deque.pop()
}
deque.push(i)
if (i >= k - 1) {
result.push(nums[deque[0]])
}
}
return result
}复杂度分析：
|
function maxSlidingWindow(nums, k) {
const half = Math.ceil(nums.length / 2) + 1;
const result = [], result2 = [];
let arr = [], reverseArr = [];
for (let i = 0; i < half; ++i) {
arr.push(nums[i])
reverseArr.push(nums[nums.length - i - 1])
if(i >= k - 1) {
result.push(Math.max(...arr))
result2.push(Math.max(...reverseArr))
arr.shift()
reverseArr.shift()
}
}
if (nums.lenght % 2 !== 0) result2.pop();
return result.concat(result2.reverse());
} |
var maxSlidingWindow = function (nums, k) {
// window存储下标
let window = [], res = [];
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
// 判断窗口是不是超出长度
if (window[0] <= i - k) {
window.shift();
}
// 从右开始比较，当当前元素大于队列底元素时，直接弹出
while(num>nums[window[window.length - 1]]) {
window.pop();
}
window.push(i);
// 当在窗口内时，加入元素
if (i >= k - 1) {
// 加入队顶元素
res.push(nums[window[0]]);
}
}
return res;
}; |
题目地址(239. 滑动窗口最大值)https://leetcode-cn.com/problems/sliding-window-maximum/ 题目描述前置知识
公司
思路符合直觉的想法是直接遍历 nums, 然后然后用一个变量 slideWindow 去承载 k 个元素， JavaScript: var maxSlidingWindow = function (nums, k) {
// bad 时间复杂度O(n * k)
if (nums.length === 0 || k === 0) return [];
let slideWindow = [];
const ret = [];
for (let i = 0; i < nums.length - k + 1; i++) {
for (let j = 0; j < k; j++) {
slideWindow.push(nums[i + j]);
}
ret.push(Math.max(...slideWindow));
slideWindow = [];
}
return ret;
};Python3: class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if k == 0: return []
res = []
for r in range(k - 1, len(nums)):
res.append(max(nums[r - k + 1:r + 1]))
return res但是如果真的是这样，这道题也不会是 hard 吧？这道题有一个 follow up，要求你用线性的时间去完成。 其实，我们没必须存储窗口内的所有元素。 如果新进入的元素比前面的大，那么前面的元素就不再有利用价值，可以直接移除。这提示我们使用一个单调递增栈来完成。 但由于窗口每次向右移动的时候，位于窗口最左侧的元素是需要被擦除的，而栈只能在一端进行操作。 而如果你使用数组实现，就是可以在另一端操作了，但是时间复杂度仍然是 因此，我们考虑使用链表来实现，维护两个指针分别指向头部和尾部即可，这样做的时间复杂度是 因此思路就是用一个双端队列来保存 具体做法：
经过上面的分析，不难知道双端队列其实是一个递减的一个队列，因此队首的元素一定是最大的。用图来表示就是： 关键点解析
代码JavaScript: JS 的 deque 实现我这里没有写， 大家可以参考 collections/deque var maxSlidingWindow = function (nums, k) {
// 双端队列优化时间复杂度, 时间复杂度O(n)
const deque = []; // 存放在接下来的滑动窗口可能成为最大值的数
const ret = [];
for (let i = 0; i < nums.length; i++) {
// 清空失效元素
while (deque[0] < i - k + 1) {
deque.shift();
}
while (nums[deque[deque.length - 1]] < nums[i]) {
deque.pop();
}
deque.push(i);
if (i >= k - 1) {
ret.push(nums[deque[0]]);
}
}
return ret;
};复杂度分析
Python3: class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = collections.deque() # 本质就是单调队列
ans = []
for i in range(len(nums)):
while q and nums[q[-1]] <= nums[i]: q.pop() # 维持单调性
while q and i - q[0] >= k: q.popleft() # 移除失效元素
q.append(i)
if i >= k - 1: ans.append(nums[q[0]])
return ans复杂度分析
扩展为什么用双端队列因为删除无效元素的时候，会清除队首的元素（索引太小了）或者队尾(元素太小了)的元素。 因此需要同时对队首和队尾进行操作，使用双端队列是一种合乎情理的做法。 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 |
|
这一题用了两种方案， 第一种方案算是暴力写法，也是大多数人常规思路 第二种方案是用了 基于队列的方式 其实，我们没必须存储窗口内的所有元素。 如果新进入的元素比前面的大，那么前面的元素就不再有利用价值，可以直接移除，这样队列对应的值其实就是一个单调递减的队列， const maxSlidingWindow = (nums: number[], k: number) => {
const result = [];
for (let i = 0; i < nums.length - k + 1; i++) {
const tmpArr = [];
for (let j = i; j < i + k; j++) {
tmpArr.push(nums[j]);
}
result.push(Math.max(...tmpArr));
}
return result;
};队列 我这里用双向链表自己实现了一个方便自己操作的首位数据的队列数据结构 class Node {
public next: Node | undefined;
public prev: Node | undefined;
constructor (public element: number) {}
}
class LinkedList {
public head: Node | undefined;
public tail: Node | undefined;
public length: number = 0;
append (element: number) {
const node = new Node(element);
if (!this.head || !this.tail) {
this.head = node;
this.tail = node;
this.length++;
return;
}
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
this.length++;
}
shift () {
if (!this.head || !this.tail) return;
const next = this.head.next;
if (!next) {
this.head = undefined;
this.tail = undefined;
this.length--;
return;
}
next.prev = undefined;
this.head = next;
this.length--;
}
pop () {
if (!this.head || !this.tail) return;
const prev = this.tail.prev;
if (!prev) {
this.head = undefined;
this.tail = undefined;
this.length--;
return;
}
prev.next = undefined;
this.tail = prev;
this.length--;
}
top () {
return this.head;
}
bottom () {
return this.tail;
}
}
const maxSlidingWindow = (nums: number[], k: number) => {
const queue = new LinkedList(); // 队列
const result = [];
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
let topNode = queue.top();
if (topNode && (i - topNode.element >= k)) {
queue.shift();
}
let bottomNode = queue.bottom();
while (bottomNode && nums[bottomNode.element] < num) {
queue.pop();
bottomNode = queue.bottom();
}
queue.append(i);
topNode = queue.top();
if (topNode && i >= k - 1) {
result.push(nums[topNode.element]);
}
}
return result;
};
console.log(maxSlidingWindow([1], 1))
console.log(maxSlidingWindow([1,-1], 1))
console.log(maxSlidingWindow([9,11], 2))
console.log(maxSlidingWindow([4,-2], 2))
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
console.log(maxSlidingWindow([5,1,2,1,5], 3))
// 输出
// [ 1 ]
// [ 1, -1 ]
// [ 11 ]
// [ 4 ]
// [ 3, 3, 5, 5, 6, 7 ]
// [ 5, 2, 5 ] |
给定一个数组
nums和滑动窗口的大小k，请找出所有滑动窗口里的最大值。示例:
解释:
提示：
你可以假设
k总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。附赠leetcode地址：leetcode
The text was updated successfully, but these errors were encountered: