What is the optimal approach for solving Sliding Window Maximum?

The optimal approach is to use a deque to maintain the indices of the elements in the current window. This allows efficient access to the maximum value for each window.

What is the time complexity of the brute force solution for this problem?

The brute force solution has a time complexity of O(n * k), where n is the length of the array and k is the window size.

Can a priority queue be used for this problem?

Yes, a priority queue (heap) can be used to solve the problem, but it results in a time complexity of O(n log k).

What is the sliding window pattern in this problem?

The sliding window pattern refers to maintaining a window of size `k` and updating the window's state as it moves from left to right over the array.

How does GhostInterview help with solving Sliding Window Maximum?

GhostInterview guides you through understanding efficient approaches, such as using deques and priority queues, and helps avoid common mistakes while maintaining the sliding window state.

#239

Hard

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

滑动窗口最大值

给你一个整数数组 nums ，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。示例 1：输入： nums = [1,3,-1,-3,5,3,6,7], k = 3 输出： [3,3,5…

数组队列滑动窗口堆（优先队列）单调队列

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
1 <= k <= nums.length

lightbulb

解题思路

方法一：优先队列（大根堆）

我们可以使用优先队列（大根堆）来维护滑动窗口中的最大值。

先将前 $k-1$ 个元素加入优先队列，接下来从第 $k$ 个元素开始，将新元素加入优先队列，同时判断堆顶元素是否滑出窗口，如果滑出窗口则将堆顶元素弹出。然后我们将堆顶元素加入结果数组。

时间复杂度 $O(n \times \log k)$ ，空间复杂度 $O(k)$ 。其中 $n$ 为数组长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = [(-v, i) for i, v in enumerate(nums[: k - 1])]
        heapify(q)
        ans = []
        for i in range(k - 1, len(nums)):
            heappush(q, (-nums[i], i))
            while q[0][1] <= i - k:
                heappop(q)
            ans.append(-q[0][0])
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate can identify and utilize efficient data structures like deque and priority queues for sliding window problems.
question_mark
The candidate understands the importance of optimizing time complexity for large inputs.
question_mark
The candidate can evaluate trade-offs between different approaches based on performance characteristics.

warning

常见陷阱

外企场景

error
Misunderstanding the problem's constraints and attempting inefficient brute force solutions for large inputs.
error
Overcomplicating the solution with unnecessary data structures or algorithms.
error
Failing to maintain the sliding window correctly, causing incorrect results when the window moves.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the minimum value in the sliding window instead of the maximum.
arrow_right_alt
Modify the problem to handle non-integer values, such as floating-point numbers or strings.
arrow_right_alt
Change the window size `k` dynamically while the array is being processed.

help

常见问题

外企场景

继续练习

#862 和至少为 K 的最短子数组 #1425 带限制的子序列和 #1438 绝对差不超过限制的最长连续子数组