剑指 Offer 59 - I. 滑动窗口的最大值

剑指 Offer 59 - I. 滑动窗口的最大值

思路：

---

题解：

优先队列O（nlogn）

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int,int>> queue;//利用优先队列大顶堆的特性
        for(int i=0;i<k;i++){
            queue.emplace(nums[i],i);
        }
        vector<int>res;
        res.push_back(queue.top().first);
        for(int i=k;i<nums.size();i++){
            queue.emplace(nums[i],i);
            while(queue.top().second<=i-k)//<=说明这个元素此时不在窗口内,
                //一直pop直到符合
                queue.pop();
            res.push_back(queue.top().first);
        }
        return res;
    }
    
};

单调队列O（n）

由于我们需要求出的是滑动窗口的最大值，如果当前的滑动窗口中有两个下标 ii 和 jj，其中 ii 在 jj 的左侧（i <j），并且 ii 对应的元素不大于 jj 对应的元素（nums[i]<nums[j]），那么会发生什么呢？

当滑动窗口向右移动时，只要 ii 还在窗口中，那么 jj 一定也还在窗口中，这是 ii 在 jj 的左侧所保证的。因此，由于 \textit{nums}[j]nums[j] 的存在，\textit{nums}[i]nums[i] 一定不会是滑动窗口中的最大值了，我们可以将 \textit{nums}[i]nums[i] 永久地移除

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();//在deque中维护一个递减的队列
                //
            }
            q.push_back(i);//q中存储的是数据的位置，便于判断是否在窗口中，数字的具体值是不必要的，只需要比较大小关系
        }

        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;
    }
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/hua-dong-chuang-kou-de-zui-da-zhi-by-lee-ymyo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。