Day 13 | Leetcode 239, 347, summary

链接

知识

239. 滑动窗口最大值

347.前 K 个高频元素

栈与队列总结

初次尝试

239. 滑动窗口最大值

本题应该有些类似于滑动窗口的经典题目：209.长度最小的子数组。本题的思路：用一个长度始终为3的队列，滑过数组。每次算出队列中的最大值，然后存入数组中。我打算另写一个函数来返回三个值中的最大值。但是应该是有办法在队列进出元素的时候顺便维护其中的最大值。

我根据暴力做法的思路，写下了如下的代码：

class Solution {
public:
    // 得出队列中的最大值
    int queuemax(queue<int> q)
    {
        int max = q.front();
        while (q.size())
        {
            q.pop();
            int tmp = q.front();
            if (max < tmp) max = tmp;
        }
        return max;
    }

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        queue<int> q;
        vector<int> res;

        for (int i = 0; i < nums.size(); i ++ )
        {
            if (q.size() < k) q.push(nums[i]);
            else if (q.size() == k)
            {
                res.push_back(queuemax(q));
                q.push(nums[i]);
                q.pop();
            }
        }
        res.push_back(queuemax(q));
        return res;
    }
};

上述代码在输入数组不大时可以正常运行，但输入数组太大时会超时，测试样例通过了37 / 51。上述暴力做法的时间复杂度是O(n * k)。看代码随想录的视频讲解吧。

347.前 K 个高频元素

拿到这道题，我的第一想法是拿哈希去做。但发现哈希不能解决本题，因为对统计频率的数组排序后，数组的下标（即输入数组的元素）被打乱了。直接看卡尔的讲解。

实现

239. 滑动窗口最大值

本题是第一道hard。难点：如何求窗口中的最大值？暴力做法时间复杂度O(n k)。需要一个特殊的队列，实现pop, push和getMaxValue（返回当前队列中的最大值）这三个操作。还可以用一个优先级队列。cpp中的优先级队列就是大顶堆（单调递减）或者小顶堆（单调递增）。大顶堆本质就是一个排序后的二叉树，最大的元素在上面。始终维护大顶堆，让大顶堆不断插入元素和弹出元素，大顶堆最前面的元素就是滑动窗口的最大值。*但是用大顶堆是不行的，因为无法正确地弹出元素（大顶堆内部自动做了排序，打乱了原来元素的顺序）。

因此用优先队列是不行的，需要我们自行实现一个单调队列来解决问题。需要维持队列中的元素是单调递增或单调递减的，同时需要保证pop操作的正确。单调队列中只需要维护有可能成为最大值的元素，而不需要维护k个元素。

模拟单调队列：
假设输入数组为13-1-35321。首先在队列中加入元素1，再加入3，若队列的前面有小于3的元素，则将这些元素全部弹出。这样做可以让队列的出口处就是最大值。由于随着滑动窗口的移动，本身就会舍弃第1个1，因此没必要维护3之前比3小的元素。接着在队列中加入-1。此时队列的前面没有小于-1的元素，故-1可以保留在队列中。此时取队首元素3，就是最大值。接着加入-3，队列前面的元素都大于-3，故保留-3，此时队列的最大值还是3。接着加入5，由于5比队列前面的元素都大，因此需要pop掉除5以外的全部元素，此时取队列的最大值，即队首元素，是5。接着放入3，3<5，放入3，此时队列的最大值还是5。接着加入2，2<5&&2<3，因此放入2，此时队列的最大值还是5。再向后移动，需要把最大值5pop掉，加入1，1<2 && 1<3，因此队列中加入1，此时队列的最大值是队首元素3。

单调队列在数组中移动的规则：除去常规的移动窗口的pop和push操作外，若push进来的元素比队列前面的元素都大，那前面的元素都要pop出去，直到队列前面的元素都大于push进来的元素为止。本方法的好处在于getMaxValue时取队首元素即可。

根据原理，我画出了如下的示意图，可以帮助理解（下图中打x的元素是因为单调队列的特殊规则：若push进来的元素比队列前面的元素都大，那前面的元素都要pop出去而被提前被删去的元素）。

根据上述原理，我尝试写出相应的代码，但是有一个问题我始终无法解决：根据规则：若push进来的元素比队列前面的元素都大，那前面的元素都要pop出去，有时原本的队首元素已经被更新为最大的元素了，意味着滑动窗口本身最前面的元素已经被弹出了，但有时，滑动窗口本身最前面的元素还没有被弹出，它仍作为队首元素，需要手动弹出。如何判断是否需要手动弹出队首元素。我来看看卡尔的代码实现，看他是如何解决这个问题的。

卡尔写了单调队列的三个关键函数。单调队列是在双向队列的基础上实现的，双向队列的首尾都可以出入元素。

deque<int> que; // cpp中队列默认用deque双向队列来实现，双向队列的首尾都可以出元素和入元素

void pop(int val) 
{
    // 只有当需要pop的元素和队首元素（单调队列中目前的最大值）相同时，才弹出队首元素
    // 例如上图的倒数第二行到最后一行的操作（532->321）
    // 若需要pop的元素小于队首元素，那么在push时该元素已经被删除了
    // 例如上图中的-1-35->-353，本来需要手动删除-1，但由于-1<5，因此在push(5)时-1已经被删除了
    if (!que.empty() && val == que.front())
        que.pop_front();
}

void push(int val)
{
    // 当队列不为空且要插入的值val > 队列中的最后一个元素时，持续从队尾弹出元素
    // 例如上图中的3-1-3->-1-35，要插入5，持续从队尾弹出比5小的元素，然后再插入5
    while (!que.empty() && val > que.back()) que.pop_back();
    que.push_back(val);
}

int getMaxValue(deque<int> que)
{
    return que.front();
}

在上述关键代码的基础上，我写下了解决本题的完整代码：

class Solution {
private:
    class MyQueue
    {
    public:
        deque<int> que;
            // 单调队列中只维护当前队列中的最大值，作为队首元素
            // 故窗口滑动时只需要在滑出最大值时手动删除最大值即可
            // 其他值都会在push时被删除
        void pop(int val)
        {
            if (!que.empty() && val == que.front()) que.pop_front();
        }

            // 保证单调队列从队首到队尾是单调递减的
            // 新插入的元素若大于当前队列中的最大值，则删除当前队列，将插入的元素放在队列的首部
        void push(int val)
        {
            while (!que.empty() && val > que.back()) que.pop_back();
            que.push_back(val);
        }

            // 当前队列中的最大值为队首元素，故返回队首元素即可
        int getMaxValue()
        {
            return que.front();
        }
    };
    
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> res;

        for (int i = 0; i < k; i ++ )
            que.push(nums[i]);

        res.push_back(que.getMaxValue());

        for (int i = k; i < nums.size(); i ++ )
        {
            que.pop(nums[i - k]);
            que.push(nums[i]);
            res.push_back(que.getMaxValue());
        }
        return res;
    }
};

347.前 K 个高频元素

两个难点：

如何求数组中每个元素的频率
如何对这个频率进行排序，并求前k个高频的元素

用map来进行排序，key用来存放元素，value用来存放元素出现的次数。接着以value为基准做从大到小的排序（不好做，因为map默认是按照key的顺序来进行排序的），最后输出value对应的key即可。时间复杂度O(nlogn)。

求前k个高频的元素，只需维护k个有序的集合，没必要对所有元素都进行排序。经典的数据结构：大顶堆、小顶堆。堆擅长在很大的数据集中求前k个高/低频的元素。大顶堆的根节点是最大的元素，小顶堆的根节点是最小的元素。

如何用堆解决这个问题？用堆去遍历map中的所有元素（以value为基准进行统计），堆中维持k个元素，遍历完map中的所有元素后，堆中的k个元素就是前k个高频元素。大/小顶堆？用大顶堆遍历map中的所有元素时，遇到新元素时，将其插入到大顶堆中，会弹出堆顶的元素（最大的元素），用大顶堆遍历完map后，堆中剩下的元素是前k个低频的元素。因此要用小顶堆。小顶堆每次在push进来元素时，弹出堆顶元素（最小的元素），堆中剩下的就是最大的元素。最后输出前k个最大的value对应的key。时间复杂度：遍历数组O(n)，每次堆中元素调整O(logk)（堆中有k个元素，堆是树状结构），总时间复杂度为O(nlogk)。在数组很大，k较小的情况下，本做法的性能明显优于对整个map进行排序的性能。优先级队列的底层实现是堆，因此用优先级队列即可。可自行实现大顶堆和小顶堆。

参考代码随想录的代码，我写下了如下的代码：

class Solution {
public:
    class compare
    {
    public: 
        // 为定义小顶堆重载运算符，这里的函数名为operator()，而非operator
        // 对大顶堆，本来应该是右边的元素>左边的元素，对小顶堆，则与此相反
        bool operator() (pair<int, int> lhs, pair<int, int> rhs)
        {
            return lhs.second > rhs.second; // 比较的是元素出现的次数，而非元素的值
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;

        // nums[i]作为key, 出现此处作为value存入map中
        for (int i = 0; i < nums.size(); i ++ )
            map[nums[i]] ++ ;
        
        // 定义小顶堆，其中的元素类型是pair<int, int>，底层实现是vector<pair<int, int>>
        priority_queue<pair<int,int>, vector<pair<int, int>>, compare> q;

        // 遍历map，不断将map中的元素插入小顶堆中，小顶堆不断弹出根节点处最小的元素
        // 最后剩下的k个元素是出现频次最高的k个元素
        for (auto it = map.begin(); it != map.end(); it ++ )
        {
            q.push(*it);
            if (q.size() > k) q.pop();
        }

        vector<int> res(k);

        // 根节点处是最小的元素，越往下元素越大，因此将小顶堆中的k个元素倒着插入res中
        for (int i = k - 1; i >= 0; i -- )
        {
            res[i] = q.top().first; // 插入res的是key, 即nums[i]
            q.pop();
        }
        return res;
    }
};

心得与备忘录

239. 滑动窗口最大值

单调队列需要手动实现，cpp标准库中没有现成可用的单调队列。
单调队列的好处在于能够将当前队列中的最大值放在队首，且不改变其他值的排列顺序（即其他值在单调队列中的排列顺序和它们在输入数组中的排列顺序相同）。
单调队列的特殊规则：若push进来的元素比队列前面的元素都大，那前面的元素都要pop出去。
定义一个类，在双向队列的基础上实现单调队列，而不要试图在主函数中对queue<int>做加工。
本题的详细模拟流程见实现中的图片。
单调队列中定义了三个函数：pop, push和getMaxValue。
对pop函数（负责模拟窗口的滑动，删除队首的最大值），需要注意：
- 单调队列中只维护当前队列中的最大值，作为队首元素
- 故窗口滑动时只需要在滑出最大值时手动删除最大值即可
- 其他值都会在push时被删除
对push函数（负责向单调队列中插入元素，同时调整队列中元素的顺序，将最大值置于队首），需要注意：
- 保证单调队列从队首到队尾是单调递减的
- 新插入的元素若大于当前队列中的最大值，则删除当前队列，将插入的元素放在队列的首部
- 当前队列中的非最大值会在不断调用push函数的过程中被删除，最大值则需要pop函数来删除
时间复杂度: O(n) 空间复杂度: O(k)
输入数组中的每个元素在单调队列中最多也就被插入和弹出各一次，没有任何多余操作，所以整体的时间复杂度还是O(n)。空间复杂度因为我们定义一个辅助队列，所以是O(k)。
本题之所以选择在双向队列的基础上加工出单调队列,是因为双向队列可以方便地在队首和队尾插入和删除元素。
注意类的写法、双向队列的push_back, push_front, pop_back, pop_front以及单调队列的push, pop等方法，不要写错或者混淆。

347.前 K 个高频元素
本题的大致思路：用map来存储元素的值和出现次数，用一个小顶堆遍历map，最终获取出现次数最高的k个元素。
map->priority_queue->vector
本题的思路：用map的key存储元素的值，value存储元素出现的次数。定义一个小顶堆。遍历map，不断将map中的元素插入到小顶堆中，不断弹出小顶堆根节点处的元素，最后小顶堆中剩下的k个元素就是出现次数最高的k个元素。将这k个元素倒着插入结果数组中即可。
为什么使用小根堆：小跟堆根节点处的元素最小，每次弹出元素也是从根节点处弹出，因此用大小为k的小根堆遍历完map后，小根堆中的k个元素是出现次数最高的k个元素，较小的元素在遍历的过程中就已经被弹出了。
注意小顶堆的定义方式：在优先级队列的基础上，传入的参数分别为小顶堆中存储的元素类型，小顶堆的底层实现，自定义的compare类（用于实现小顶堆根节点是最小元素的特性）。
注意如何写compare类，关键在于重载运算符。
注意vector数组是可以定义大小的，定义方式为vector<int> res(k)，vector元素定义了大小之后，就能像普通数组那样用索引给元素赋值：res[i]，插入元素的push_back函数并不是必须的。
根据小根堆的特点，res数组需要倒着插入，即从下标k - 1处开始插入。
定义类是，要记得在类中的函数前加上public，否则无法正常调用类中的函数。
本算法的时间复杂度是O(nlogk)，好于对map全部排序的O(nlogn)，在n较大，k较小时性能提升尤为明显。

栈与队列总结

栈和队列的理论基础：栈先入后出，队列先入先出
用两个栈实现队列，用一个队列实现栈
栈的应用：栈的应用相对较为简单且单一。栈特别适合处理对相邻字符需要做特殊判断的一些问题。比如相邻的括号匹配（20. 有效的括号）、相邻字符的消除（删除字符串中的所有相邻重复项）和后缀表达式中相邻数字的计算（逆波兰表达式求值）。
队列的应用：队列的应用更为复杂且多样，包括手动实现单调队列（239. 滑动窗口最大值）和手动实现大/小顶堆（优先级队列）347. 前k个高频元素）。对于队列的应用要多复习，这两题写起来都较为复杂。
单调队列不是一成不变的，而是不同场景不同写法。不要以为239. 滑动窗口最大值中的单调队列实现就是固定的写法。
栈里面的元素在内存中是连续分布的么？

这个问题有两个陷阱：
- 陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中不一定是连续分布的。
- 陷阱2：缺省情况下，默认底层容器是deque，那么deque在内存中的数据分布是什么样的呢？答案是：不连续的，下文也会提到deque。
拓展题：71. 简化路径
优先级队列就是大/小顶堆，名字虽为队列（因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列），但本质是完全二叉树。大顶堆（堆头是最大元素），小顶堆（堆头是最小元素）。从小到大排就是小顶堆，从大到小排就是大顶堆。大小顶堆和大小根堆是相同的。