Repository navigation
239. 滑动窗口最大值 #95
Description
单调队列
1.维护一个单调递减队列，从大到小，左边是出口，右边是入口
2.每次 pop 时需要判断当前队列是否为空，并且如果当前要弹出的数值等于队列出口元素时，队列移除出口元素
3.每次 push 的元素如果大于入口元素，将队列后端的数值弹出，直到 push 的元素数值小于队列入口元素，保证单调性
4.max 可以获取当前队列的最大值
const maxSlidingWindow = function(nums, k) {
const n = nums.length
class slideWindow {
constructor() {
this.data = []
}
push(val) {
let data = this.data
while (data.length > 0 && data[data.length - 1] < val) {
data.pop()
}
data.push(val)
}
pop(val) {
let data = this.data
if (data.length > 0 && data[0] === val) {
data.shift()
}
}
max() {
return this.data[0]
}
}
let res = []
let windows = new slideWindow()
for (let i = 0; i < n; i++) {
if (i < k - 1) {
windows.push(nums[i])
} else {
windows.push(nums[i])
res.push(windows.max())
windows.pop(nums[i - k + 1])
}
}
return res
}- 时间复杂度：O(n)
- 空间复杂度：O(n)
Activity