maxSlidingWindow

239. 滑动窗口最大值

分析

维护一个单调递减队列：
- 使用一个双端队列 q 存储数组的索引
- 队列中的元素对应的值保持单调递减顺序，队首始终是当前窗口的最大值索引
窗口滑动的处理：
- 窗口失效处理：检查队首索引是否超出当前窗口范围 (i - k + 1)，若超出则弹出队首
- 保持单调性：将新元素加入队列时，弹出队列中所有小于当前元素值的索引，以确保队列的单调递减性
- 记录最大值：当窗口的大小达到 k 时 (i >= k - 1)，窗口的最大值即为队首索引对应的值

时间复杂度

遍历数组：所有元素仅被插入和弹出队列一次，时间复杂度为 O(n)
队列操作：每次插入和弹出操作的平均时间复杂度为 O(1)

总时间复杂度：O(n)

空间复杂度

使用了一个双端队列存储索引，空间复杂度为 O(k)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution
{
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k)
    {
        std::deque<int> q;            // 双端队列存储索引
        std::vector<int> res;         // 存储结果

        for (int i = 0; i < nums.size(); ++i)
        {
            // 移除队首超出窗口范围的元素
            if (q.size() && q.front() < i - k + 1)
                q.pop_front();

            // 保持队列单调递减
            while (q.size() && nums[q.back()] <= nums[i])
                q.pop_back();

            // 添加当前元素索引到队列
            q.push_back(i);

            // 当窗口形成时，记录窗口最大值
            if (i >= k - 1)
                res.push_back(nums[q.front()]);
        }

        return res;
    }
};