代码随想录算法训练营第十三天-创新互联

LeetCode 239. 滑动窗口大值

10年积累的网站建设、成都做网站经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先建设网站后付款的网站建设流程,更有建德免费网站建设让你可以放心的选择与我们合作。

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


视频讲解https://www.bilibili.com/video/BV1XS4y1p7qj/?vd_source=f98f2942b3c4cafea8907a325fc56a48文章讲解https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html

  • 思路:不必维护窗口里的所有元素,只需要维护有可能成为窗口里大值的元素就可以了
    • 单调队列:用 deque 维护一个队首→队尾,单调递减的队列 que
      • void pop(int val):如果 val 为大值,弹出队首元素,即 que.pop_front()
      • void push(int val):
        • que 中的元素都比 val 早进入滑动窗口,也早离开滑动窗口,故而只需维护大于 val 的值,比 val 小的值是没有机会成为滑动窗口大值的
        • while (队尾元素< val) {弹出队尾元素}
        • 将 val 插入到队尾
      • int getMax():返回队首元素
    • i< k,只 push(nums[i])
    • 添加 [0, k - 1] 大值到 result
    • i 从 k 向后遍历,先 pop(nums[i - k]),再 push(nums[i]),最后添加滑动窗口 [ i - k + 1, i] 的大值(直接调用 getMax)到 result
  • 代码:
class Solution {
private:
    // 单调队列(从大到小)
    class MyQueue {
    public:
        // 用deque来实现
        dequeque;
        // 每次弹出的时候,比较当前要弹出的数值是否等于队列出口元素的数值,如果相等则弹出。
        // 同时pop之前判断队列当前是否为空。
        void pop(int val) {
            if (!que.empty() && val == que.front()) {
                que.pop_front();
            }
        }
        // 如果push的数值大于入口元素的数值,那么就将队列后端的数值弹出,直到push的数值小于等于队列入口元素的数值为止。
        // 这样就保持了队列里的数值是单调从大到小的了。
        void push(int val) {
            while (!que.empty() && que.back()< val ) {
                que.pop_back();
            }
            que.push_back(val);
        }
        // 查询当前队列里的大值 直接返回队列前端也就是front就可以了。
        int getMax() {
            return que.front();
        }
    };
public:
    vectormaxSlidingWindow(vector& nums, int k) {
        MyQueue que;
        // 滑动窗口大值序列
        vectorresult;
        // 先将前k的元素放进队列
        for (int i = 0; i< k; ++i) {
            que.push(nums[i]);
        }
        result.push_back(que.getMax());
        // 移动滑动窗口
        for (int i = k; i< nums.size(); ++i) {
            que.pop(nums[i - k]);
            que.push(nums[i]);
            result.push_back(que.getMax());
        }
        return result;
    }
};

LeetCode 347.前 K 个高频元素

题目描述:给定一个非空的整数数组 nums,返回其中出现频率前 k 高的元素。

视频讲解https://www.bilibili.com/video/BV1Xg41167Lz文章讲解https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html

  • 思路:
    • 统计 {元素值, 出现次数}:不需要按key值排序,unordered_map即可
    • 排序,维护出现次数前k大的(用小顶堆,频率低的优先级高)
    • 需要自定义比较规则,可以参考下这篇文章:c++优先队列(priority_queue)用法详解
    • 注意:优先队列中存储的是pair,而最后结果只需要key
  • 代码:
// 时间复杂度:O(nlogk)
// 空间复杂度:O(n)
class Solution {
public:
    // 小顶堆
    class mycomparison {
    public:
        bool operator()(const pair& lhs, const pair& rhs) {
            // 频率低的优先级高
            return lhs.second >rhs.second;
        }
    };
    vectortopKFrequent(vector& nums, int k) {
        // 要统计元素出现频率
        unordered_mapmap; // mapfor (int i = 0; i< nums.size(); i++) {
            map[nums[i]]++;
        }

        // 对频率排序
        // 定义一个小顶堆,大小为k
        priority_queue, vector>, mycomparison>pri_que;

        // 用固定大小为k的小顶堆,扫面所有频率的数值
        for (unordered_map::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() >k) { // 如果堆的大小大于了K,则队列弹出,保证堆的大小一直为k
                pri_que.pop();
            }
        }

        // 找出前K个高频元素,因为小顶堆先弹出的是最小的,所以倒序来输出到数组
        vectorresult(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;

    }
};

总结

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧

分享题目:代码随想录算法训练营第十三天-创新互联
新闻来源:/article48/dgcchp.html

成都网站建设公司_创新互联,为您提供品牌网站建设全网营销推广搜索引擎优化网站营销品牌网站设计定制网站

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联

h5响应式网站建设