LeetCode239. 滑动窗口最大值【优先队列】

港控/mmm° 2023-01-22 12:53 106阅读 0赞

难度：困难  
题目描述：

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210519231359563.png]

class Solution { 
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) { 
            if(k==1){ 
                return nums;
            }
            priority_queue<pair<int,int>> st;
            vector<int> ans;
            int n=nums.size();
            for(int i=0;i<k;i++){ 
                st.emplace(nums[i],i);
            }
            ans.push_back(st.top().first);
            for(int i=k;i<n;i++){ 
                st.emplace(nums[i],i);
                while(st.top().second<=i-k){ 
                    st.pop();
                }
                ans.push_back(st.top().first);
            }
            return ans;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]: /images/20221020/3b43ca43bdb74c66a6f13863c077a38e.png
[20210519231359563.png]: /images/20221020/ed0592a4c1734b41890bc6bb87d68c2b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，106人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode239. 滑动窗口最大值

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ] > [牛客在线编程算法篇【题号NC开头】][NC] > [剑指offer【题号 JZ开头】][offer_

我不是女神ヾ/ 2024年03月27日 10:21/ 0 赞/ 159 阅读

相关 LeetCode - 239 滑动窗口最大值

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [239. 滑动窗口最大值 - 力扣（Lee

超、凢脫俗/ 2023年09月27日 18:20/ 0 赞/ 71 阅读

相关 leetcode239. 滑动窗口最大值

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

淩亂°似流年/ 2023年07月06日 09:49/ 0 赞/ 70 阅读

相关 LeetCode239. 滑动窗口最大值

题目描述：给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返

àì夳堔傛蜴生んèń/ 2023年06月30日 05:27/ 0 赞/ 103 阅读

相关 LeetCode239. 滑动窗口最大值【优先队列】

难度：困难题目描述： > 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k > 个数字。滑动

港控/mmm°/ 2023年01月22日 12:53/ 0 赞/ 107 阅读

相关 LeetCode239. 滑动窗口最大值

目录问题描述解题思路 -------------------- 问题描述给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧

客官°小女子只卖身不卖艺/ 2022年12月12日 04:52/ 0 赞/ 250 阅读

相关 239. 滑动窗口最大值（优先队列）

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

痛定思痛。/ 2022年09月11日 13:14/ 0 赞/ 258 阅读

相关 LeetCode-239. 滑动窗口最大值(单调队列)

[LeetCode-239. 滑动窗口最大值][LeetCode-239.] 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可

朴灿烈づ我的快乐病毒、/ 2022年04月24日 07:04/ 0 赞/ 297 阅读

相关 Leetcode 239 滑动窗口最大值

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

以你之姓@/ 2022年04月22日 12:48/ 0 赞/ 290 阅读

相关 leetcode 239. 滑动窗口最大值

![1588437-20190410201239992-520179513.png][] 一：暴力解法，能ac但是时间复杂度O(nk) class Solution

爱被打了一巴掌/ 2021年12月21日 01:21/ 0 赞/ 337 阅读