XingHuiSama の博客

给你一个整数数组 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 <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

困难题，第一开始思路是往红黑色方向解，居然也通过了

红黑树

class 滑动窗口最大值 {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int front =0;
        int rear =k-1;

        vector<int> ans;
        map<int, int> mp;

        for (int i = 0; i <= rear; i++) {
            mp[nums[i]]++;
        }

        ans.push_back(mp.rbegin()->first);

        while (rear < nums.size()-1) {
            rear++;
            if (mp.find(nums[front]) != mp.end()) {
                if (mp[nums[front]] == 1) {
                    mp.erase(nums[front]);
                }
                else {
                    mp[nums[front]]--;
                }
            }
            front++;
            mp[nums[rear]]++;
            ans.push_back(mp.rbegin()->first);
        }
        return ans;
    }
};

1. 算法核心思想：双指针定长平移与动态有序集合

采用显式的双指针（front 和 rear）来精确控制滑动窗口的物理边界，并结合 C++ 标准库中基于红黑树实现的 std::map 来实时维护窗口内的数值状态。考虑到窗口内可能存在重复数字，算法以数值本身作为键，以其在窗口中出现的频次作为值。红黑树会自动维持键的升序排列，从而保证当前窗口的最大值始终位于树的最右侧，随时可以通过反向迭代器 O(1) 获取。

2. 宏观运行机制

构建初始窗口：利用双指针划定前 k 个元素的初始范围，遍历并将这批元素录入红黑树进行频率统计。组装完成后，直接通过反向迭代器 rbegin() 获取树中键值最大的节点，存入结果集。
匀速滑动步进：在右指针触及数组末尾前，窗口整体向右平移。右探针率先前推一步锁定新元素，随后回头清算左指针指向的过期元素。清理逻辑遵循频率约束：如果过期元素在树中的频率仅剩 1，则将其节点彻底抹除（erase）；若频率大于 1，则仅削减其频率。完成旧元素退场后，左指针跟进维持窗口定长，并将锁定的右侧新元素录入红黑树。最后，重新提取当前状态下的红黑树最大值追加到结果集中。整个过程严格保持“一进一出”的动态平衡。

3. 复杂度剖析

时间复杂度：O(Nlogk)。窗口滑动的循环执行 N−k 次。每次循环中，红黑树的查找（find）、删除（erase）和插入（mp[]++）操作的时间消耗均为 O(logk)。整体耗时受红黑树内部结构的自平衡调整成本主导。
空间复杂度：O(k)。通过及时清理过期且频率归零的元素，红黑树 mp 的节点数量被双指针严格限制在最多 k 个以内。

单调列表

class 滑动窗口最大值 {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int front = 0;
        int rear = k - 1;

        vector<int> ans;
        deque<int> dq;

        for (int i = 0; i <= rear; i++) {
            while (!dq.empty()) {
                if (nums[dq.back()] >= nums[i]) {
                    dq.push_back(i);
                    break;
                }
                else {
                    dq.pop_back();
                }
            }
            if (dq.empty()) {
                dq.push_back(i);
            }
        }

        ans.push_back(nums[dq.front()]);
        
        while (rear < nums.size() - 1) {
            front++;
            if (dq.front() < front) {
                dq.pop_front();
            }
            rear++;
            while (!dq.empty()) {
                if (nums[dq.back()] >= nums[rear]) {
                    dq.push_back(rear);
                    break;
                }
                else {
                    dq.pop_back();
                }
            }
            if (dq.empty()) {
                dq.push_back(rear);
            }
            ans.push_back(nums[dq.front()]);
        }

        return ans;
    }
};

1. 算法核心思想：索引存取与内卷淘汰机制

彻底抛弃了排序思维，转而使用双端队列 deque 来构建一个单调递减的候选人队列。队列中不直接存储数组元素的值，而是存储元素的索引。通过维持队列内部值的单调递减性，确保队首永远是当前窗口内的最大值；通过存储索引，能够精准计算出当前的最大值是否已经滑出了窗口的物理边界。

2. 宏观运行机制

阶段一：组装初创窗口 利用循环和右指针 rear 划定前 k 个元素的初始范围。当新元素准备入队时，将其值与队尾索引对应的值进行持续比对。若发现队尾元素小于新元素，直接将其开除（执行 pop_back）；若遇到大于等于新元素的队尾值，新元素则乖乖排在后面（执行 push_back 并触发 break 跳出比对）；若队列被清空，说明新元素是当前最大值，直接入队。此阶段结束时，队首记录的即为前 k 个元素中的最大值索引，将其对应数值存入结果集。
阶段二：严密步进与首尾双重清理 进入核心的 while 循环，窗口开始整体向右滑动。左指针 front 率先右移收缩边界，并立刻对队首的“最强者”进行身份核验。一旦发现队首索引已经小于当前有效的 front，说明该最大值已过期，立刻执行 pop_front 强制其退休。随后右指针 rear 步进扩张边界。此时复用阶段一的职场淘汰逻辑，清理掉队列尾部所有小于新进入元素的值，并将新元素的索引安排入队。每次窗口更替完毕，再次读取队首索引对应的值作为当前局部最优解，追加到结果集中。

3. 复杂度剖析

时间复杂度：O(N)。虽然代码中在外层循环内嵌套了负责淘汰的 while 循环，但重点在于数组中的每一个元素生命周期被严格约束：最多只会被 push_back 入队一次，且最多被 pop_back 或 pop_front 移出队列一次。均摊至每一步，内部操作耗时为常数级别，整体时间消耗与数组长度呈绝对的线性关系。
空间复杂度：O(k)。得益于及时的过期清理和弱者淘汰机制，双端队列的容量被严格控制。即使在极端单调递减的数组测试中，队列长度也绝不会超过当前窗口的设定大小 k。