239. 滑动窗口最大值(Hard)

题目思路

单调栈，维持一个单调栈，记录滑动窗口的最大值。

美团面试考到过，尴尬的是没做出来。

代码

双指针，我们知道 j 的范围一定是从 0，到 n - 1。因为窗口大小差 k ，所以 i 的范围是 j - k + 1。

此外，只有当 i >= 0 的时候，才可以加入元素。

import collections
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = collections.deque()
        n = len(nums)
        ans = []
        for i, j in zip(range(-k + 1, n - k + 1), range(n)): # j:[0, n - 1] i = j - k + 1
            while q and nums[j] > q[-1]:
                q.pop()
            q.append(nums[j])
            if i >= 0: # 当 i > 0 的时候，可以开始加入
                ans.append(q[0])
                if nums[i] == q[0]: # 加入完了以后，就可以删除了
                    q.popleft()
        return ans

第二种实现方式，是分两步走。

• 第一步先将 k 个元素加入队列中。
• 第二步滑动窗口的同时， 维持一个单调递减的双端队列 q，同时还要不停的输出答案。

func maxSlidingWindow(nums []int, k int) []int {
    // 1. 将前 k 个元素先加入队列中， 维持一个单调递减的双端队列 q
    n := len(nums)
    q := make([]int, 0)
    ans := make([]int, 0)
    for i := 0; i < k; i++{
        for len(q) > 0 && nums[i] > nums[q[len(q) - 1]] { // 当大于最后一个值的时候，将元素删除
            q = q[:len(q) - 1]
        }
        q = append(q, i) // 加入
    }
    ans = append(ans, nums[q[0]])
		
  	// 2. 滑动窗口的同时， 维持一个单调递减的双端队列 q
    for i := k; i < n; i ++ {
        for len(q) > 0 && nums[i] > nums[q[len(q) - 1]] {
            q = q[:len(q) - 1]
        }
        q = append(q, i)
        if q[0] <= i - k {
            // q[0] == i - k 代表最大值正好是最左的元素，现在将其删除
            // q[0] < i - k 代表的是超出 k 个元素的范围了，也同样删除 
            // 这一行代码很精妙。用索引代替了数值。即可以确定是否越界，又存储了数值。
            q = q[1:]
        }
        ans = append(ans, nums[q[0]])
    } 
    return ans 
}