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

今天是算法训练的第十三天。

目录

前言

一、滑动窗口最大值

解题思路：

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

二、前 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//确定窗口大小
        {
            push(nums[i]);
        }
        ans.push_back(front());
        for(int i=k;isize();i++)        //滑动窗口
        {
            
            pop(nums[i-k]);                //移出窗口的值，传去与队列比较
            push(nums[i]);                //插入
            ans.push_back(front());        //保留最大值
        }
        return ans;
    }
};

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

二、前 K 个高频元素（未解决）

关于大顶堆与小顶堆还未解决，晚点哇！

---

总结

二叉树我来了！