八月社招沃尔玛过经：优先队列求滑动窗口最大值 + 优化

面试概况

最近社招 SDE2 发面试的不少，Amazon、Walmart、Google L6 都有。A 哥讲讲 Walmart 考的一道优先队列题。在职跳槽或者刚被 layoff 的同学可以学习一下！

题目全程口述，需要自己 take notes 记笔记。

题目

给定数组和窗口大小 k，计算每个窗口内的最大值（滑动窗口最大值）。

解法 1：优先队列（大顶堆）

把 (值, 下标) 放进大顶堆。每次取堆顶前，先把下标已经滑出窗口的元素弹掉。

import heapq

def max_sliding_window_heap(nums, k):
    heap, res = [], []
    for i, x in enumerate(nums):
        heapq.heappush(heap, (-x, i))
        while heap[0][1] <= i - k:      # 懒删除：堆顶过期才弹出
            heapq.heappop(heap)
        if i >= k - 1:
            res.append(-heap[0][0])
    return res

时间 O(n log n)，空间 O(n)。

Follow-up：Optimize solution

用单调递减队列（双端队列）。队列里存下标，对应的值从队头到队尾递减：

• 新元素入队前，把队尾比它小的元素都弹掉，因为它们以后不可能成为最大值。
• 队头下标滑出窗口时弹出队头。
• 队头就是当前窗口的最大值。

from collections import deque

def max_sliding_window(nums, k):
    dq, res = deque(), []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

每个元素最多入队、出队各一次，时间 O(n)，额外空间 O(k)。

复杂度对比

解法	时间	空间
暴力	O(nk)	O(1)
优先队列	O(n log n)	O(n)
单调队列	O(n)	O(k)