239. Sliding window maximum
Tags:
Hard
Skills:
Queue
Links:
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Approach - deque
Implement
1function maxSlidingWindow(nums: number[], k: number): number[] {
2 /**
3 Approach: deque
4 1. Remove items with less than nums[i] in window
5 2. Remove items not exist in window
6 3. When finished current window, maximum number is number at index 0 of dequeue
7 */
8
9 const dequeue: number[] = [] // SC: O(k)
10 const result: number[] = []
11 for (let i = 0; i < nums.length; i++) { // O(n)
12 while (dequeue.length > 0 && nums[dequeue.at(-1)] < nums[i]) { // O(k)
13 dequeue.pop()!;
14 }
15
16 while (dequeue.length > 0 && dequeue[0] < i - k + 1) { // O(k)
17 dequeue.shift()!
18 }
19
20 dequeue.push(i)
21 if (i >= k - 1) {
22 result.push(nums[dequeue[0]]);
23 }
24 }
25 return result;
26};Time and space complexity
O(n) (mỗi phần tử vào và ra deque tối đa một lần).O(k) (deque tối đa chứa k phần tử).Lưu ý
nums[dequeue.at(-1)] < nums[i]Đây là điều kiện để xác định rằng chúng mình sẽ loại bỏ phần tử ở vị trí cuối cùng trong dequeue nếu nó nhỏ hơn nums[i] (đây là value của phần tử ở thời điểm hiện tại)
Lý do chúng mình có thể bỏ phần tử ở dequeue là vì dù chúng mình có thêm vào trong dequeue thì nó cũng không có ý nghĩa khi chúng mình đang mong muốn tìm max(window_sliding)
dequeue[0] < i - k + 1Điều kiện này dùng để kiếm tra xem index trong dequeue có còn nằm trong window_sliding nữa hay không. Khi chúng mình thực hiện loại bỏ các phần từ ở điều kiện nums[dequeue.at(-1)] < nums[i] điều này có nghĩa rằng giá trị lớn nhất chắc chắn sẽ nằm tại dequeue[0] . Do đó điều kiện này sẽ kiểm tra xem index có còn nằm trong window_sliding nữa không, nếu không còn nằm trong chúng mình sẽ loại bỏ nó đi
Trong bài tập này chúng mình sẽ có cơ hội vận dụng được dequeue với xử lý giá trị ở 2 đầu của mảng