LeetCode Hot 100 P239 Sliding Window Maximum

---

Timeline

Timeline

2026-03-11

init

Monotonic queue, max heap, lazy deletion

---

Problem:

P239 Sliding Window Maximum

https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked

Max heap + lazy deletion

#include <vector>
#include <queue>
#include <unordered_map>
using std::vector;
using std::priority_queue;
using std::unordered_map;

class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int> &nums, int k)
        {
                priority_queue<int> max_heap;
                unordered_map<int, int> umap;
                vector<int> ret;

                int n = nums.size();

                for (int i = 0; i < k; i++) {
                        max_heap.push(nums[i]);
                        umap[nums[i]]++;
                }

                for (int i = 0; i <= n - k; i++) {
                        while (!max_heap.empty() && umap[max_heap.top()] == 0)
                                max_heap.pop();

                        ret.push_back(max_heap.top());

                        if (i + k < n) {
                                umap[nums[i]]--;

                                max_heap.push(nums[i + k]);
                                umap[nums[i + k]]++;
                        }
                }

                return ret;
        }
};

Actually, there is no need to use umap for lazy deletion. If the max heap stores the value along with the index, lazy deletion can be achieved.

#include <vector>
#include <queue>
#include <utility>

using std::vector;
using std::priority_queue;
using std::pair;

class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int> &nums, int k)
        {
                int i, n = nums.size();
                priority_queue<pair<int, int> > q;

                for (i = 0; i < k; ++i)
                        q.emplace(nums[i], i);

                vector<int> ans = { q.top().first };

                for (i = k; i < n; ++i) {
                        q.emplace(nums[i], i);

                        while (q.top().second <= i - k) // No need to delete immediately; you can determine whether it is inside based on its index.
                                q.pop();

                        ans.push_back(q.top().first);
                }
                return ans;
        }
};

Complexity O(n log n)

The recommended approach is a monotonic queue: using a monotonic decreasing deque.

deque<int> qIt stores the array index, not the actual value.

This queue maintains a property: the values corresponding to the indices in the queue are monotonically decreasing. That is,nums[q[0]] >= nums[q[1]] >= ...。

Monotonic queue

#include <vector>
#include <queue>

using std::vector;
using std::deque;

class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int> &nums, int k)
        {
                int n = nums.size();
                deque<int> q;
                for (int i = 0; i < k; ++i) {
                        while (!q.empty() && nums[i] >= nums[q.back()])
                                q.pop_back();

                        q.push_back(i);
                }

                vector<int> ans = { nums[q.front()] };

                for (int i = k; i < n; ++i) {
                        while (!q.empty() && nums[i] >= nums[q.back()])
                                q.pop_back();

                        q.push_back(i);
                        while (q.front() <= i - k)
                                q.pop_front();

                        ans.push_back(nums[q.front()]);
                }
                return ans;
        }
};

acm mode rewrite

#include <cstdio>
#include <queue>
#include <utility>
#include <vector>

using std::vector;
using std::priority_queue;
using std::pair;

int main()
{
        int i, n, k;
        priority_queue<pair<int, int>, vector<pair<int, int> >, std::less<pair<int, int> > >
                max_heap;

        scanf("%d %d", &n, &k);

        vector<int> vec(n);

        for (i = 0; i < n; i++)
                scanf("%d", &vec[i]);

        for (i = 0; i < k; i++)
                max_heap.push({ vec[i], i });

        printf("%d ", max_heap.top().first);

        for (; i < n; i++) {
                while (!max_heap.empty() && i - max_heap.top().second >= k) // Note: check max_heap.empty() to avoid an infinite loop.
                        max_heap.pop();

                max_heap.push({ vec[i], i });

                printf("%d ", max_heap.top().first);
        }
}