代码随想录算法训练营第13天 | LeetCode - 239.滑动窗口最大值，347.前 K 个高频元素，栈和队列总结

239.滑动窗口最大值

代码随想录链接

题目

LeetCode 239

在给定的一个数组中，进行一个大小为k的滑动窗口的移动，将每次移动过程中窗口的最大值保存下来并返回。

自己的思路

暴力法，然后Time Limit Exceeded.

使用一个队列，随着窗口的移动，队列也同时移动，并且队列的队首应该是当前窗口中的最大值。

要实现这样一个数据结构，需要自己定义一个队列并进行维护。这个队列只需要维护可能成为最大值的元素，保证队列里的元素从大到小进行排列。

在pop时，如果窗口移出的元素等于单调队列的出口元素，则将该元素从队列弹出，否则不进行任何操作；在push时，若窗口加入的元素大于队尾元素，则将队尾的元素依次取出，直到对空或队尾元素大于窗口加入的元素，再将该元素push入队。这样操作后，队首即为当前窗口的最大值。

为了实现这样一个数据结构，即满足需要在队首队尾进行操作的条件，使用deque来实现这个队列最合适。 关于deque和queue的区别，可以参照这个文章

解法

class MonotonicQueue {                              // 单调队列
private:
    deque<int> que;                                 // 使用deque实现
public:
    void pop(int val) {
        if (!que.empty() && que.front() == val) {   // 当队列不为空且队首等于滑动窗口移出的值时，弹出队首
            que.pop_front();
        }
    }

    void push (int val) {
        while (!que.empty() && val > que.back()) {  // 若不满足队尾元素大于窗口加入的元素的条件，就不断弹出队尾直到满足条件后再将该值加入队伍
            que.pop_back();
        }
        que.push_back(val);
    }

    int front() {                                   // 设计的队列的队首在任意时刻都是对应时刻滑动窗口中的最大值
        return que.front();
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MonotonicQueue mq;
        vector<int> result;
        for (int i = 0; i < k; i++) mq.push(nums[i]); // 将前k个数据加入
        result.push_back(mq.front());                 // 取前k个数据的最大值
        for (int i = k; i < nums.size(); i++) {       // 使用一个for循环来移动窗口
            mq.pop(nums[i - k]);                      // 从队列中移出滑动窗口移出的值
            mq.push(nums[i]);                         // 将滑动窗口中新加入的值加入队列
            result.push_back(mq.front());             // 取此时队列的最大值，并放入结果数组中
        }
        return result;
    }
};

该方法的时间复杂度为\(O(n)\)，空间复杂度为\(O(k)\)。

347.前 K 个高频元素

代码随想录链接

题目

LeetCode 347

给定一个数组和一个数字K，返回在该数组中出现频率最高的前k个数字。

自己的思路

统计元素的出现次数可以使用map来实现，而按照出现次数来排列前k个元素可以使用优先级队列。

为什么不用快排来对所有出现的元素的频率进行排序？因为我们最后只求前k个，可以只维护前k个可能的元素就好。

优先级队列在默认情况下是使用大顶堆进行排序，在这个题目中，如果每次更新大顶堆时，都将最大的元素弹出，不能保留高频元素。所以要使用小顶堆，将最小的元素弹出，剩下的才是最大的元素。

解法

class MinHeapComp {                                                                 // 根据map的结构定义大小如何对比
public:
    bool operator()(const pair<int, int>& lhs, const pair<int, int> &rhs) {
        return lhs.second > rhs.second;
    }
};
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        for (int i : nums) {                                                        // 将所有元素的出现次数进行统计
            map[i]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, MinHeapComp> que;    // 使用优先级队列来实现小顶堆排序
        for (auto it = map.begin(); it != map.end(); it++) {                        // 遍历map，将map中的值推入
            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;
    }
};

栈和队列总结

理论基础

栈和队列都是容器适配器，其底层实现可以有:

• vector

• deque

• list

不同的实现方式，对于数据的实际存储方式是有影响的。C++中，栈和队列的默认底层实现都是deque。

栈与队列相互实现

例如用栈来实现队列，用队列来实现栈，这种题目考察的是对于栈和队列特性的了解和使用。

例题:

• 栈实现队列

• 队列实现栈

括号匹配问题

这是使用栈来解决的经典问题。

例题：

• 括号匹配问题

字符串去重

将字符串按顺序放到一个串中，若要放入的字符与栈顶相同，就丢弃这两个字符。

例题：

• 字符串去重

逆波兰表达式

按照逆波兰表达式的顺序求出对应式子的答案，也是栈的经典应用题目。

例题：

• 逆波兰表达式求解

滑动窗口最大值

这个题目中一个比较重要的应用是单调队列，即单调递增或单调递减的队列。

例题：

• 滑动窗口最大值

求前k个高频元素

这个题目里面着重讲了优先级队列，优先级队列其实就是个堆，内部元素自动按照元素的权值进行排列。

• 求前K个高频元素