leetcode239：滑动窗口最大值

题目链接

leetcode

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值 。

C++ 代码

#include <iostream>
#include <deque>
#include <vector>
#include <queue>
using namespace std;

/*
    优先队列：大根堆实时维护元素中的最大值。

    初始时，将数组的前 k 个元素放入优先队列。
    每次向右移动窗口时，将一个新的元素放入队列，此时堆顶的元素就是堆中所有元素的最大值。
    不断地移除堆顶的元素，直到该元素出现在滑动窗口中。
    此时，堆顶元素就是滑动窗口中的最大值。

    时间复杂度：O(nlogk)
        其中 n 是输入数组的长度，k 是窗口的大小。
        在每次循环中，插入和删除元素的时间复杂度都是 O(logk)，总的时间复杂度为 O(nlogk)。
    空间复杂度：O(k)
        k 是窗口的大小，存储最大堆。
        不考虑返回答案的空间 O(n)，只计算额外的空间。
*/
class Solution_0 {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        // 初始化窗口
        for (int i = 0; i < k; i++) {
            q.emplace(nums[i], i);
        }

        vector<int> res;
        res.push_back(q.top().first);
        // 开始滑动窗口
        for (int i = k; i < n; i++) {
            q.emplace(nums[i], i);
            // 移除堆顶不在窗口内的元素
            while (q.top().second <= i-k) {
                q.pop();
            }
            res.push_back(q.top().first);
        }

        return res;
    }
};

/*
    滑动窗口

    使用双端队列：
        为了同时弹出队首和队尾的元素，使用双端队列。
        队列存储可能成为窗口最大值的元素下标。
        队列的头部始终是当前窗口的最大值。
    维护队列：
        遍历数组，不断地更新队列，确保队列中的元素从大到小。
    处理窗口滑动：
        当窗口向前滑动时，移除不在窗口内的元素，添加新进入窗口的元素。
    
    时间复杂度：O(n)
        其中 n 是数组的长度，每个元素最多被加入和移除队列一次。
    空间复杂度：O(k)
        队列中最多不超过 k 个元素。
*/
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> dq; // 存储索引

        for (int i = 0; i < 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);

            // 添加结果（第 k 个元素开始）
            if (i >= k-1) {
                res.push_back(nums[dq.front()]);
            }
        }

        return res;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = { 
        {1,3,-1,-3,5,3,6,7},
        {1}
    };
    vector<int> k_cases = { 3, 1 };

    for (int i = 0; i < nums_cases.size(); i++) {
        auto& nums = nums_cases[i];
        int k = k_cases[i];
        vector<int> result = solution.maxSlidingWindow(nums, k);

        cout << "Input: nums = ";
        printArray(nums);
        cout << ", k = " << k << endl;
        cout << "Output: ";
        printArray(result);
        cout << endl;
    }
    
    return 0;
}