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

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元起,快前往官网查看详情吧


文章题目:代码随想录算法训练营第十三天-创新互联
当前网址:http://scyanting.com/article/dgcchp.html