第十三天| 239. 滑动窗口最大值 、347.前 K 个高频元素

Leetcode?239. 滑动窗口最大值

题目链接：239 滑动窗口最大值

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

• 1 <= nums.length <= 105
• -104?<= nums[i] <= 104
• 1 <= k <= nums.length

思考：自定义队列MyQueue，存放有可能成为窗口里最大值的元素。

设计单调队列的时候，pop，和push操作要保持如下规则：

1. pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
2. push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。

主函数中，先将前k个元素存入MyQueue对象中，用容器存储第一个最大值，之后从k+1个元素开始遍历数组，每次出队窗口最前面的元素，入队窗口后面一个元素，再得到最大值存入容器。

代码：

class Solution {
private:
    class MyQueue {     //单调队列(递减)
    public:
        deque<int> dq;      

        void push(int value) {
            while (!dq.empty() && dq.back() < value)        //将入口处小于参数的元素弹出
                dq.pop_back();
            dq.push_back(value);
        }

        void pop(int value) {
            if (!dq.empty() && dq.front() == value)        //将与参数一致的队头元素出队
                dq.pop_front();
        }
        
        int front() {
            return dq.front();
        }
    };
    
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> result;
        for (int i = 0; i < k; i++) { // 先将前k的元素放进队列
            que.push(nums[i]);
        }
        result.push_back(que.front());
        for (int i = k; i < nums.size(); i++) {
            //移动窗口
            que.pop(nums[i - k]);
            que.push(nums[i]);
            result.push_back(que.front());
        }
        return result;
    }
};

Leetcode?347.前 K 个高频元素

题目链接：347 前 K 个高频元素

题干：给你一个整数数组?nums?和一个整数?k?，请你返回其中出现频率前?k?高的元素。你可以按?任意顺序?返回答案。

• 1 <= nums.length <= 105
• k?的取值范围是?[1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前?k?个高频元素的集合是唯一的

思考：使用容器map来统计元素出现的频率。为降低时间复杂度，采取固定大小为K的小根堆，当然要自定义比较器。遍历数组时将键值对入堆，每当堆大小大于k时出堆顶元素。最后将剩下的高频元素存储到容器vector中返回。

代码：

class Solution {
public:
    class cmp {     //自定义比较器
    public:
        bool operator()(const pair<int,int>& l,const pair<int,int>& r) {
            return l.second > r.second;
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> map;     //统计各元素出现次数
        for (int i = 0; i < nums.size(); i++) 
            map[nums[i]]++;

        priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> que;      //小根堆

        //遍历map 固定大小为k的小根堆存储最大频率的键值对
        for (unordered_map<int,int>::iterator it = map.begin(); it != map.end(); it++) {
            que.push(*it);
            if (que.size() > k)
                que.pop();      //弹出最小值
        }

        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = que.top().first;
            que.pop();
        }
        return result;
    }
};

栈与队列专题总结

• 滑动窗口，重新理解用数据结构维护元素的情况，只维护有用的元素
• 优先级队列，了解到本质为一个披着队列外衣的堆。优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列，且优先级队列内部元素是自动依照元素的权值排列。
• 单调队列，不把单调队列的作用局限于排序，还需要研究
• 大/小根堆，考虑到时间复杂度，在使用堆时要考虑存储元素个数