LeetCode 239: Sliding Window Maximum (Monotonic Deque)
LeetCode 239ArrayQueueMonotonic QueueToday we solve LeetCode 239 - Sliding Window Maximum.
Source: https://leetcode.com/problems/sliding-window-maximum/
English
Problem Summary
Given an integer array nums and an integer k, there is a sliding window of size k moving from left to right by one position each step. Return the maximum value in each window.
Key Insight
Use a monotonic decreasing deque of indices. The deque front is always the index of current window maximum. Before pushing a new index, pop all smaller (or equal) values from the back because they can never be maximum in any future window that includes the new value.
Brute Force and Why Insufficient
Brute force scans each window of length k and computes max directly. This takes O(nk). With large n and k, this becomes too slow.
Optimal Algorithm (Step-by-Step)
1) Keep a deque storing indices, and ensure values are decreasing from front to back.
2) For current index i, first remove expired front index if it is outside window: deque.front <= i-k.
3) Remove back indices while nums[deque.back] <= nums[i].
4) Push i to back.
5) When i >= k-1, record nums[deque.front] as the current maximum.
Complexity Analysis
Time: O(n) because each index enters and exits deque at most once.
Space: O(k) for the deque.
Common Pitfalls
- Storing values instead of indices, then you cannot detect expiry by position.
- Forgetting to remove expired front index before recording max.
- Using wrong boundary for expiry (i-k logic off by one).
- Appending answer before the first full window is formed.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0 || k == 0) return new int[0];
int[] ans = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>(); // store indices
for (int i = 0; i < n; i++) {
if (!dq.isEmpty() && dq.peekFirst() <= i - k) {
dq.pollFirst();
}
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
dq.pollLast();
}
dq.offerLast(i);
if (i >= k - 1) {
ans[i - k + 1] = nums[dq.peekFirst()];
}
}
return ans;
}
}func maxSlidingWindow(nums []int, k int) []int {
n := len(nums)
if n == 0 || k == 0 {
return []int{}
}
deque := make([]int, 0) // indices
ans := make([]int, 0, n-k+1)
for i := 0; i < n; i++ {
if len(deque) > 0 && deque[0] <= i-k {
deque = deque[1:]
}
for len(deque) > 0 && nums[deque[len(deque)-1]] <= nums[i] {
deque = deque[:len(deque)-1]
}
deque = append(deque, i)
if i >= k-1 {
ans = append(ans, nums[deque[0]])
}
}
return ans
}class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq; // indices
vector<int> ans;
for (int i = 0; i < (int)nums.size(); ++i) {
if (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
while (!dq.empty() && nums[dq.back()] <= nums[i]) {
dq.pop_back();
}
dq.push_back(i);
if (i >= k - 1) {
ans.push_back(nums[dq.front()]);
}
}
return ans;
}
};from collections import deque
from typing import List
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
dq = deque() # store indices
ans = []
for i, x in enumerate(nums):
if dq and dq[0] <= i - k:
dq.popleft()
while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(i)
if i >= k - 1:
ans.append(nums[dq[0]])
return ansvar maxSlidingWindow = function(nums, k) {
const deque = []; // store indices
const ans = [];
for (let i = 0; i < nums.length; i++) {
if (deque.length && deque[0] <= i - k) {
deque.shift();
}
while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
deque.pop();
}
deque.push(i);
if (i >= k - 1) {
ans.push(nums[deque[0]]);
}
}
return ans;
};中文
题目概述
给定整数数组 nums 和窗口大小 k，窗口从左到右每次移动一格，返回每个窗口中的最大值。
核心思路
使用单调递减双端队列（存下标）。队首始终是当前窗口最大值下标；新元素进入前，队尾所有小于等于它的元素都可以淘汰。
暴力解法与不足
暴力法对每个窗口扫描 k 个元素取最大值，时间复杂度 O(nk)，当输入规模较大时会超时。
最优算法（步骤）
1）队列存下标，并保持对应值从队首到队尾单调递减。
2）遍历到下标 i 时，先弹出窗口外过期下标（<= i-k）。
3）持续弹出队尾中比当前值小或相等的下标。
4）把当前下标入队。
5）当 i >= k-1 时，队首即当前窗口最大值。
复杂度分析
时间复杂度：O(n)，每个下标最多入队、出队一次。
空间复杂度：O(k)。
常见陷阱
- 队列里存值不存下标，无法判断元素是否过期。
- 记录答案前忘记先清理过期元素。
- 过期判断写错边界，导致 off-by-one。
- 窗口尚未形成时就写入答案。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0 || k == 0) return new int[0];
int[] ans = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>(); // store indices
for (int i = 0; i < n; i++) {
if (!dq.isEmpty() && dq.peekFirst() <= i - k) {
dq.pollFirst();
}
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
dq.pollLast();
}
dq.offerLast(i);
if (i >= k - 1) {
ans[i - k + 1] = nums[dq.peekFirst()];
}
}
return ans;
}
}func maxSlidingWindow(nums []int, k int) []int {
n := len(nums)
if n == 0 || k == 0 {
return []int{}
}
deque := make([]int, 0) // indices
ans := make([]int, 0, n-k+1)
for i := 0; i < n; i++ {
if len(deque) > 0 && deque[0] <= i-k {
deque = deque[1:]
}
for len(deque) > 0 && nums[deque[len(deque)-1]] <= nums[i] {
deque = deque[:len(deque)-1]
}
deque = append(deque, i)
if i >= k-1 {
ans = append(ans, nums[deque[0]])
}
}
return ans
}class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq; // indices
vector<int> ans;
for (int i = 0; i < (int)nums.size(); ++i) {
if (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
while (!dq.empty() && nums[dq.back()] <= nums[i]) {
dq.pop_back();
}
dq.push_back(i);
if (i >= k - 1) {
ans.push_back(nums[dq.front()]);
}
}
return ans;
}
};from collections import deque
from typing import List
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
dq = deque() # store indices
ans = []
for i, x in enumerate(nums):
if dq and dq[0] <= i - k:
dq.popleft()
while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(i)
if i >= k - 1:
ans.append(nums[dq[0]])
return ansvar maxSlidingWindow = function(nums, k) {
const deque = []; // store indices
const ans = [];
for (let i = 0; i < nums.length; i++) {
if (deque.length && deque[0] <= i - k) {
deque.shift();
}
while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
deque.pop();
}
deque.push(i);
if (i >= k - 1) {
ans.push(nums[deque[0]]);
}
}
return ans;
};
Comments