算法随想Day11【栈与队列】| LC239-滑动窗口最大值、LC347-前 K 个高频元素

LC239. 滑动窗口最大值

思路分析：

1、暴力出奇迹，对n个元素各遍历k次，记录最大值，复杂度O(n * k)

2、如果存在一种数据结构，能模拟滑动串口，且能提供pop()、push()、getMaxValue()三种接口，该题目就简单易得了。但现在不存在这样一种数据结构

3、使用优先级队列（大顶堆/小顶堆），push()的时候容器内的元素会自动排好序，滑动窗口变化时，难以找到窗口最末尾的元素pop掉

4、单调队列，相当于 DIY一种队列。

class Solution
{
private:
    ////模拟单调栈的实现
    class MyQueue
    {
    public:
        deque<int> que;
        ////每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
        void pop(int value)
        {
            if (que.empty() != true && value == que.front())
            {
                que.pop_front();
            }
        }

        ////如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
        void push(int value)
        {
            while(que.empty() != true && value > que.back())
            {
                que.pop_back();
            }
            que.push_back(value);
        }

        ////查询当前队列里的最大值 直接返回队列前端也就是front就可以了
        int getMaxValue()
        {
            return que.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k)
    {
        MyQueue myque;
        vector<int> vec;
        int size = nums.size();
        int count = 0;
        while (count < k)
        {
            myque.push(nums[count]);
            count++;
        }
        vec.push_back(myque.getMaxValue());
        for (int i = k; i < size; i++)
        {
            myque.pop(nums[i - k]);
            myque.push(nums[i]);
            vec.push_back(myque.getMaxValue());
        }
        return vec;
    }
};

优先队列的模拟实现：

• 让值最大的元素，永远在queue的front()处
• 优先队列只维护当前的最大值，和在该值后续插入的比自己小的值。在push某个值时，应该从尾部back()开始判断，去除在该值之前插入的比自己小的值。
• 窗口模拟滑动时，应该先pop掉尾元素，再push进新的头元素。pop时，需要判断当前pop的元素是否位于front()处，若不是说明在之前的push操作中，该元素早就被刷掉了。

官方 -- 优先队列实现方法

vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
    ////堆里的元素可以是(value, index)二元组，检查当前需要pop的
    ////元素的index还在不在，在就一直pop，最后返回在范围里的堆顶
    int size = nums.size();
    vector<int> vec;
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < k; i++)
    {
        pq.emplace(nums[i], i);
    }
    vec.push_back(pq.top().first);
    for (int i = k; i < size; ++i)
    {
        pq.emplace(nums[i], i);
        while (pq.top().second <= i - k)
        {
            pq.pop();
        }
        vec.push_back(pq.top().first);
    }
    return vec;size
}

时间复杂度：O(nlog n)，其中 n是数组 nums 的长度。在最坏情况下，数组 nums 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(logn)，因此总时间复杂度为 O(nlogn)

LC347. 前 K 个高频元素

对元素出现的频率进行排序，用map数据结构比较合适；如采用map<key, value>，对所有元素进行一次遍历，记录出现的频率后面对value进行一个排序输出。假设采用快排的方法，时间复杂度最佳是O(nlogn)。

但其实对n个元素，我们只需要维护k个最高配的元素，为了减少在排序上消耗的时间。

大顶堆、小顶堆数据结构，擅长在很大的一个数据集里面，求前k个高频或低频的元素。我们只需要用堆来存放二元的数据节点（pair<int, int>），遍历map并根据value值排序好，这个时候我们只需要维护k个元素。时间复杂度是O(nlogk)，当元素个数n >> k时，这种方法的优势即有充分体现。

本题首刷，了解思路，学习优先队列和map容器结合的综合应用。

• 定义priority_queue时，应为要用其存放pair数据类型，由于pair不是基本数据类型，所以需要自定义比较方式。pair类本身没有重载"<"，所以只能通过仿函数的方式实现自定义比较方法。

class Solution
{
public:
    ////使用仿函数的方式，自定义比较方法
    class MyComparison
    {
    public:
        ////使用常量引用const &是为了提高效率(不用改变比较两者本身值)
        bool operator()(const pair<int, int>& left, const pair<int, int>& right)
        {
            return left.second > right.second;
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k)
    {
        unordered_map<int, int> umap;
        for (int i = 0; i < nums.size(); i++)
        {
            umap[nums[i]]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, MyComparison> pri_que;

        for (auto it : umap)
        {
            pri_que.push(it);
            if (pri_que.size() > k)
            {
                pri_que.pop();
            }
        }

        vector<int> vec(k, 0);
        for (int i = k - 1; i >= 0; i--)
        {
            vec[i] = pri_que.top().first;
            pri_que.pop();
        }

        return vec;
    }
};