Day13——滑动窗口最大值&&前 K 个高频元素(未解决)

简介: Day13——滑动窗口最大值&&前 K 个高频元素(未解决)

今日文案:


梦魂拘检苦无方,悲喜于中不可藏。竟至泣啼如赤子,一生辛苦在初尝。

前言


太忙了最近,而且我开始跟不上了,哭泣,落下了好多天的学习记录,开始补了,加油加油!

一、滑动窗口最大值


题目描述:

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

返回 滑动窗口中的最大值 。

题目来源:

力扣

解题思路:


1、暴力枚举:

循环移动的同时,每次遍历一遍数组,比较简单。

2、队列

在每个窗口中,插入所有元素,如果后面插入的比前面的大就全部弹出前面的,如果窗口移动移去的值==队列的头,去掉队列的头。

代码如下:

class Solution {
public:
    deque<int> que;
    void push(int x)
    {
        while(!que.empty()&&x>que.back())        //插入
        {
            que.pop_back();
        }
        que.push_back(x);
    }
    void pop(int x)
    {
        if(!que.empty()&&que.front()==x)        //比对看是否需要去掉
        {
            que.pop_front();
        }
    }
    int front()
    {
        return que.front(); 
    }
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        for(int i=0;i<k;i++)            //确定窗口大小
        {
            push(nums[i]);
        }
        ans.push_back(front());
        for(int i=k;i<nums.size();i++)        //滑动窗口
        {
            pop(nums[i-k]);                //移出窗口的值,传去与队列比较
            push(nums[i]);                //插入
            ans.push_back(front());        //保留最大值
        }
        return ans;
    }
};

这是我个人的学习笔记,写得很粗略,只能用来辅助我自己理解。

二、前 K 个高频元素(未解决)


关于大顶堆与小顶堆还未解决,晚点哇!

总结

二叉树我来了!

相关文章
|
3月前
|
算法
【算法】滑动窗口——最大连续1的个数
【算法】滑动窗口——最大连续1的个数
|
6月前
|
算法 测试技术 C#
【滑动窗口】C++算法:可见点的最大数目
【滑动窗口】C++算法:可见点的最大数目
|
6月前
|
算法
【优选算法】——滑动窗口——1004. 最大连续1的个数 III
【优选算法】——滑动窗口——1004. 最大连续1的个数 III
|
6月前
|
算法 C语言
[优选算法]------滑动窗⼝——209. 长度最小的子数组
[优选算法]------滑动窗⼝——209. 长度最小的子数组
|
6月前
leetcode代码记录(滑动窗口最大值
leetcode代码记录(滑动窗口最大值
34 0
|
6月前
|
算法 测试技术 C#
【单调栈】LeetCode2334:元素值大于变化阈值的子数组
【单调栈】LeetCode2334:元素值大于变化阈值的子数组
【单调栈】LeetCode2334:元素值大于变化阈值的子数组
|
6月前
|
算法 测试技术 C++
【动态规划】【C++算法】801. 使序列递增的最小交换次数
【动态规划】【C++算法】801. 使序列递增的最小交换次数
|
6月前
|
算法 测试技术 C#
【滑动窗口】【差分数组】C++算法:K 连续位的最小翻转次数
【滑动窗口】【差分数组】C++算法:K 连续位的最小翻转次数
|
6月前
|
算法 测试技术 C#
【map】【滑动窗口】C++算法:最小区间
【map】【滑动窗口】C++算法:最小区间
|
6月前
leetcode-6119:元素值大于变化阈值的子数组
leetcode-6119:元素值大于变化阈值的子数组
33 0