LeetCode刷题(ACM模式)-05栈与队列

发布时间:2024年01月14日

参考引用:代码随想录

  • 注:每道 LeetCode 题目都使用 ACM 代码模式,可直接在本地运行,蓝色字体为题目超链接

0. 栈与队列理论基础

21天学通C++读书笔记(二十三:自适应容器:栈和队列)
堆、栈、堆栈的区别(总结)

  • 栈和队列的原理:队列(queue)是先进先出,栈(stack)是后进先出
    在这里插入图片描述

  • 栈和队列是 STL(C++ 标准库)里面的两个数据结构,C++ 标准库是有多个版本的,要知道使用的 STL 是哪个版本,才能知道对应的栈和队列的实现原理,那么来介绍一下,三个最为普遍的 STL 版本

    • 1、HP STL:其他版本的 C++ STL,一般是以 HP STL 为蓝本实现出来的,HP STL 是 C++ STL 的第一个实现版本,而且开放源代码
    • 2、P.J.Plauger STL:由 P.J.Plauger 参照 HP STL实现出来的,被 Visual C++ 编译器所采用,不是开源的
    • 3、SGI STL:由 Silicon Graphics Computer Systems 公司参照 HP STL 实现,被 Linux 的 C++ 编译器 GCC 所采用,SGI STL 是开源软件,源码可读性高
  • 以 SGI STL 版本为例,先来说一说栈,栈后进先出
    在这里插入图片描述

    • 栈提供 push 和 pop 等接口,所有元素必须符合后进先出规则,所以栈不提供走访功能,也不提供迭代器(iterator)。不像 set 或者 map 提供迭代器 iterator 来遍历所有元素
    • 栈是以底层容器完成其所有的工作,对外提供统一的接口,底层容器是可插拔的(也就是说可以控制使用哪种容器来实现栈的功能),所以 STL 中栈往往不被归类为容器,而被归类为 container adapter(容器适配器)
    • 从下图栈的内部结构可以看出,栈的底层实现可以是 vector,deque,list,主要就是数组和链表的底层实现,常用的 SGI STL,如果没有指定底层实现的话,默认是以 deque 为栈的底层结构(deque 是一个双向队列,只要封住一端,只开通另一端就可以实现栈的逻辑)
      在这里插入图片描述
  • 队列中先进先出的数据结构,同样不允许有遍历行为,不提供迭代器, SGI STL 中队列一样是以 deque 为缺省情况下的底层结构,所以 STL 队列也不被归类为容器,而被归类为 container adapter(容器适配器)

1. 用栈实现队列

232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):

  • 实现 MyQueue 类
    void push(int x) 将一个元素 x 放入队列的末尾
    int pop() 从队列的开头移除元素
    int peek() 返回队列开头的元素
    boolean empty() 返回队列是否为空,如果队列为空,返回 true ;否则,返回 false
  • 说明
    只能使用标准的栈操作:也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
    所使用的语言也许不支持栈。可使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
  • 示例 1
    输入
    [“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
    [[], [1], [2], [], [], []]
    输出
    [null, null, null, 1, 1, false]
    解释
    MyQueue myQueue = new MyQueue();
    myQueue.push(1); // queue is: [1]
    myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
    myQueue.peek(); // return 1
    myQueue.pop(); // return 1, queue is [2]
    myQueue.empty(); // return false
  • 提示
    1 <= x <= 9
    最多调用 100 次 push、pop、peek 和 empty
    假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)

1.1 思路

  • 使用栈来模式队列的行为,需要一个输入栈和一个输出栈,这里要注意输入栈和输出栈的关系
  • 下面动画模拟以下队列的执行过程
    • queue.push(1);
    • queue.push(2);
    • queue.pop(); 注意此时的输出栈的操作
    • queue.push(3);
    • queue.push(4);
    • queue.pop();
    • queue.pop(); 注意此时的输出栈的操作
    • queue.pop();
    • queue.empty();

在这里插入图片描述

  • 在 push 数据的时候,只要数据放进输入栈就好,但在 pop 的时候,操作就复杂一些,输出栈如果为空,就把进栈数据全部导入进来(注意是全部导入),再从出栈弹出数据,如果输出栈不为空,则直接从出栈弹出数据就可以了。

  • 最后如何判断队列为空呢?如果进栈和出栈都为空的话,说明模拟的队列为空了

1.2 代码实现

// 时间复杂度: push 和 empty 为 O(1), pop 和 peek 为 O(n)
// 空间复杂度: O(n)
#include <iostream>
#include <stack>

using namespace std;

class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;

    MyQueue() {} // 构造函数,初始化成员变量

    // 将元素 x 压入输入栈 stIn 中
    void push(int x) {
        stIn.push(x);
    }
    // 用于从队列中弹出一个元素
    int pop() {
        // 如果输出栈 stOut 为空,那么就需要先将输入栈 stIn 中的所有元素取出来
        // 并压入输出栈 stOut,这样才能保证弹出的元素是队列的第一个元素
        if (stOut.empty()) {
            while (!stIn.empty()) {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        // 从输出栈中弹出一个元素并返回
        int result = stOut.top();
        stOut.pop();
        return result;
    }
    // 用于返回队列的第一个元素,但不弹出该元素
    // peek() 的实现直接复用了 pop(),要不然,对 stOut 判空的逻辑又要重写一遍   
    int peek() {
        int res = this->pop(); // 获取队列第一个元素,并保存在局部变量 res 中
        stOut.push(res); // 将 res 压回到输出栈 stOut 中,以保持队列的原始状态
        return res;
    }
    // 用于判断队列是否为空
    bool empty() {
        // 如果输入栈 stIn 和输出栈 stOut 都为空,则认为队列为空
        return stIn.empty() && stOut.empty();
    }
};

int main(int argc, char *argv[]) {
    MyQueue q;
    q.push(1);
    q.push(2);

    cout << q.pop() << endl;
    cout << q.peek() << endl;
    cout << q.empty() << endl;
    
    return 0;
}

2. 用队列实现栈

225. 用队列实现栈
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)

  • 实现 MyQueue 类
    void push(int x) 将元素 x 压入栈顶。
    int pop() 移除并返回栈顶元素。
    int top() 返回栈顶元素。
    boolean empty() 如果栈是空的,返回 true ;否则,返回 false
  • 说明
    你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
    你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可
  • 示例 1
    输入
    [“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
    [[], [1], [2], [], [], []]
    输出
    [null, null, null, 2, 2, false]
    解释
    MyStack myStack = new MyStack();
    myStack.push(1);
    myStack.push(2);
    myStack.top(); // 返回 2
    myStack.pop(); // 返回 2
    myStack.empty(); // 返回 False
  • 提示
    1 <= x <= 9
    最多调用100 次 push、pop、top 和 empty
    每次调用 pop 和 top 都保证栈不为空

2.1 思路

  • 队列模拟栈(这里要强调是单向队列),其实一个队列就够了,那么先说一说两个队列来实现栈的思路
    • 队列是先进先出的规则,把一个队列中的数据导入另一个队列中,数据的顺序并没有变,并没有变成先进后出的顺序,但是依然还是要用两个队列来模拟栈,只不过没有输入和输出的关系
  • 如下面动画所示,用两个队列 que1 和 que2 实现队列的功能,que2 其实完全就是一个备份的作用,把 que1 最后面的元素以外的元素都备份到 que2,然后弹出最后面的元素,再把其他元素从 que2 导回 que1
    • queue.push(1);
    • queue.push(2);
    • queue.pop(); // 注意弹出的操作
    • queue.push(3);
    • queue.push(4);
    • queue.pop(); // 注意弹出的操作
    • queue.pop();
    • queue.pop();
    • queue.empty();

在这里插入图片描述

2.2 代码实现

  • 两个队列实现
// 时间复杂度: push为O(n),其他为O(1)
// 空间复杂度: O(n)
#include <iostream>
#include <queue>

using namespace std;

class MyStack {
public:
    queue<int> que1;
    queue<int> que2;

    MyStack() {} // 构造函数,初始化成员变量
    // 用于向栈中添加元素,实际上是将该元素插入到 que1 队列的末尾
    void push(int x) {
        que1.push(x);
    }
    // 用于弹出栈顶元素并返回其值
    int pop() {
        // 1. 首先通过获取 que1 队列的大小来获取栈顶元素
        int size = que1.size();
        size--;
        // 2. 然后将前 size-1 个元素从 que1 弹出并推入到 que2 中
        while (size--) {
            que2.push(que1.front());
            que1.pop();
        }
        // 3. 把最后一个元素弹出并返回
        int result = que1.front();
        que1.pop();
        // 4. 最后再将 que2 的元素重新放回 que1 中
        que1 = que2;
        while (!que2.empty()) { // 清空 que2
            que2.pop();
        }
        return result;
    }
    // 用于返回栈顶元素的值,即返回 que1 队列的末尾元素
    int top() {
        return que1.back();
    }
    // 用于判断队列是否为空,如果 que1 队列为空,则返回 true
    bool empty() {
        return que1.empty();
    }
};

int main(int argc, char *argv[]) {
    MyStack s;
    s.push(1);
    s.push(2);
    s.push(3);

    cout << s.pop() << endl;
    cout << s.top() << endl;
    cout << s.empty() << endl;
    
    return 0;
}
  • 一个队列实现
// 时间复杂度: push为O(n),其他为O(1)
// 空间复杂度: O(n)
#include <iostream>
#include <queue>

using namespace std;

class MyStack {
public:
    queue<int> que;

    MyStack() {} // 构造函数,初始化成员变量
    // 用于向栈中添加元素,实际上是将该元素插入到 que1 队列的末尾
    void push(int x) {
        que.push(x);
    }
    // 用于弹出栈顶元素并返回其值
    int pop() {
        // 1. 首先通过获取 que 队列的大小来获取栈顶元素
        int size = que.size();
        size--;
        // 2. 将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部
        while (size--) {
            que.push(que.front());
            que.pop();
        }
        // 3. 把最后一个元素弹出并返回,此时弹出的元素顺序就是栈的顺序了
        int result = que.front();
        que.pop();
        return result;
    }
    // 用于返回栈顶元素的值,即返回 que 队列的末尾元素
    int top() {
        return que.back();
    }
    // 用于判断队列是否为空,如果 que 队列为空,则返回 true
    bool empty() {
        return que.empty();
    }
};

int main(int argc, char *argv[]) {
    MyStack s;
    s.push(1);
    s.push(2);
    s.push(3);

    cout << s.pop() << endl;
    cout << s.top() << endl;
    cout << s.empty() << endl;
    
    return 0;
}

3. 有效的括号

20. 有效的括号
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号

  • 示例 1
    输入:s = “()”
    输出:true
  • 示例 2
    输入:s = “()[]{}”
    输出:true
  • 示例 3
    输入:s = “(]”
    输出:false

3.1 思路

  • 由于栈结构的特殊性,非常适合做对称匹配类的题目。首先要弄清楚,字符串里的括号不匹配有几种情况,有三种不匹配的情况

    • 第一种情况,字符串里左方向的括号多余了,所以不匹配
      在这里插入图片描述

    • 第二种情况,括号没有多余,但是括号的类型没有匹配上
      在这里插入图片描述

    • 第三种情况,字符串里右方向的括号多余了,所以不匹配
      在这里插入图片描述

  • 具体实现步骤

    • 第一种情况:已经遍历完了字符串,但是栈不为空,说明有相应的左括号没有右括号来匹配,所以return false
    • 第二种情况:遍历字符串匹配的过程中,发现栈里没有要匹配的字符。所以return false
    • 第三种情况:遍历字符串匹配的过程中,栈已经为空了,没有匹配的字符了,说明右括号没有找到对应的左括号return false

那什么时候说明左括号和右括号全都匹配了呢,就是字符串遍历完之后,栈是空的,就说明全都匹配了

3.2 代码实现

// 时间复杂度: O(n)
// 空间复杂度: O(n)
#include <iostream>
#include <stack>
#include <string>

using namespace std;

class Solution {
public:
    bool isValid(string s) {
        // 如果 s 的长度为奇数,一定不符合要求
        if (s.size() % 2 != 0) {
            return false;
        }
        stack<char> st; // 定义一个栈 st 用于记录左括号
        for (int i = 0; i < s.size(); ++i) {
            // 如果是左括号 '('、'{' 或 '[',则将其对应的右括号入栈
            if (s[i] == '(') {
                st.push(')');
            } else if (s[i] == '{') {
                st.push('}');
            } else if (s[i] == '[') {
                st.push(']');
            // 如果是右括号 ')'、'}' 或 ']',则判断当前栈顶元素是否与该右括号相同
            // 如果不同或栈为空,则说明无法匹配成功,直接返回 false;否则弹出栈顶元素
            } else if (st.empty() || st.top() != s[i]) {
                return false;
            } else {
                st.pop(); // st.top() 与 s[i] 相等,栈弹出元素
            }
        }
        // 遍历完整个字符串后,若栈为空,则说明所有左括号都有对应的右括号,返回 true
        // 否则说明还有未匹配的左括号,无法匹配成功,返回 false
        return st.empty();
    }
};

int main(int argc, char *argv[]) {
    string s = "()[]{}";

    Solution solution;
    cout << boolalpha << solution.isValid(s);
    return 0;
}

4. 删除字符串中的所有相邻重复项

1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。在 S 上反复执行重复项删除操作,直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串,答案保证唯一

  • 示例
    输入:“abbaca”
    输出:“ca”
    解释:例如,在 “abbaca” 中,可以删除 “bb” 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后得到字符串 “aaca”,其中又只有 “aa” 可以执行重复项删除操作,所以最后的字符串为 “ca”
  • 提示
    1 <= S.length <= 20000
    S 仅由小写英文字母组成

4.1 思路

  • 在删除相邻重复项的时候,其实就是要知道当前遍历的这个元素,在前一位是不是遍历过一样数值的元素
    • 用栈来存放前面遍历过的元素,当遍历当前这个元素时,去栈里看一下是不是遍历过相同数值的相邻元素,然后再去做对应的消除操作,动画如下所示

在这里插入图片描述

4.2 代码实现

// 时间复杂度: O(n)
// 空间复杂度: O(1),返回值不计空间复杂度
#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    string removeDuplicates(string S) {
        string result;
        for (char s : S) {
            // 如果当前字符是第一个字符,或者与 result 中最后一个字符不相同,就将其添加到 result 中
            if (result.empty() || result.back() != s) {
                result.push_back(s);
            } else {  // 否则,就删除 result 中的最后一个字符,因为两个相邻的重复字符都必须被删除
                result.pop_back();
            }
        }
        return result;
    }
};

int main(int argc, char *argv[]) {
    string s = "abbaca";

    Solution solution;
    cout << solution.removeDuplicates(s) << endl;
}

5. 逆波兰表达式求值

150. 逆波兰表达式求值
给你一个字符串数组 tokens,表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。

  • 注意
    有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’
    每个操作数(运算对象)都可以是一个整数或者另一个表达式
    两个整数之间的除法总是 向零截断
    表达式中不含除零运算
    输入是一个根据逆波兰表示法表示的算术表达式
    答案及所有中间计算结果可以用 32 位 整数表示
  • 示例 1
    输入:tokens = [“2”,“1”,“+”,“3”,“*”]
    输出:9
    解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9
  • 示例 2
    输入:tokens = [“4”,“13”,“5”,“/”,“+”]
    输出:6
    解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6
  • 示例 3
    输入:tokens = [“10”,“6”,“9”,“3”,“+”,“-11”,“×”,“/”,“×”,“17”,“+”,“5”,“+”]
    输出:22
    解释:该算式转化为常见的中缀算术表达式为:
    ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
    = ((10 * (6 / (12 * -11))) + 17) + 5
    = ((10 * (6 / -132)) + 17) + 5
    = ((10 * 0) + 17) + 5
    = (0 + 17) + 5
    = 17 + 5
    = 22
  • 提示
    1 <= tokens.length <= 104
    tokens[i] 是一个算符(“+”、“-”、“*” 或 “/”),或是在范围 [-200, 200] 内的一个整数

逆波兰表达式

  • 逆波兰表达式是一种后缀表达式,所谓后缀就是指运算符写在后面
    平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 )
    该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * )
  • 逆波兰表达式主要有以下两个优点
    去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果
    适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中

5.1 思路

  • 逆波兰表达式相当于是二叉树中的后序遍历,可以把运算符作为中间节点,按照后序遍历的规则画出一个二叉树把二叉树序列化,本题中每一个子表达式要得出一个结果,然后拿这个结果再进行运算,这就是一个相邻字符串消除的过程

在这里插入图片描述

5.2 代码实现

#include <vector>
#include <stack>
#include <string>
#include <iostream>

using namespace std;

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> st;
        for (int i = 0; i < tokens.size(); i++) {
            // 判断 tokens[i] 是否为 “+”, “-”, “*” 或 “/”
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                // 将栈顶元素赋值给 num1,并从栈中移除该元素
                long long num1 = st.top();
                st.pop();
                // 将新的栈顶元素赋值给 num2,并从栈中移除该元素
                long long num2 = st.top();
                st.pop();

                // 根据 tokens[i] 的值执行相应的运算,并将结果入栈
                if (tokens[i] == "+") 
                    st.push(num2 + num1);
                if (tokens[i] == "-") 
                    st.push(num2 - num1);
                if (tokens[i] == "*") 
                    st.push(num2 * num1);
                if (tokens[i] == "/") 
                    st.push(num2 / num1);
            } else {  // 将 tokens[i] 转换为 long long 类型,并入栈
                st.push(stoll(tokens[i]));
            }
        }

        int result = st.top();
        st.pop();
        return result;
    }
};

int main() {
    Solution solution;
    vector<string> tokens = {"2", "1", "+", "3", "*"};
    int result = solution.evalRPN(tokens);
    cout << "Result: " << result << endl;

    return 0;
}

6. 滑动窗口最大值

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

  • 示例 1
    输入:nums = [1,3,-1,-3,5,3,6,7],k = 3
    输出:[3,3,5,5,6,7]
    解释
    在这里插入图片描述
  • 示例 2
    输入:nums = [1],k = 1
    输出:[1]

6.1 思路

  • 这是使用单调队列的经典题目:需要一个队列,这个队列放进去窗口里的元素,然后随着窗口的移动,队列也一进一出,每次移动之后,队列告诉我们里面的最大值是什么

    • 每次窗口移动的时候,调用 que.pop (滑动窗口中移除元素的数值),que.push (滑动窗口添加元素的数值),然后 que.front() 就返回想要的最大值
  • 队列没有必要维护窗口里的所有元素,只需要维护有可能成为窗口里最大值的元素就可以,同时保证队列里的元素数值是由大到小的,维护元素单调递减的队列就叫做单调队列,即单调递减或单调递增的队列

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

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

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

6.2 代码实现

// 时间复杂度: O(n)
// 空间复杂度: O(k)
#include <vector>
#include <deque>
#include <string>
#include <iostream>

using namespace std;

class Solution {
private:
    class MyQueue {  // 单调队列(从大到小)
    public:
        deque<int> que; // 使用 deque 来实现单调队列
        // 每次弹出的时候,比较当前要弹出的数值是否等于队列出口元素的数值,如果相等则弹出
        // 同时 pop 之前判断队列当前是否为空
        void pop(int value) {
            if (!que.empty() && value == que.front()) {
                que.pop_front();
            }
        }
        // 如果 push 的数值大于入口元素的数值,那么就将队列后端的数值弹出,直到 push 的数值小于等于队列入口元素的数值为止
        // 这样就保持了队列里的数值是单调从大到小的
        void push(int value) {
            while (!que.empty() && value > que.back()) {
                que.pop_back();
            }
            que.push_back(value);

        }
        // 查询当前队列里的最大值 直接返回队列前端也就是 front 就可以
        int front() {
            return que.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());      // result 记录前 k 的元素的最大值
        for (int i = k; i < nums.size(); i++) {
            que.pop(nums[i - k]);           // 滑动窗口移除最前面元素
            que.push(nums[i]);              // 滑动窗口前加入最后面的元素
            result.push_back(que.front());  // 记录对应的最大值
        }
        return result;
    }
};

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    Solution solution;
    vector<int> result = solution.maxSlidingWindow(nums, k);
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }

    return 0;
}

7. 前 k 个高频元素

347.前 K 个高频元素
给你一个整数数组 nums 和一个整数 k,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案
示例 1
输入: nums = [1,1,1,2,2,3],k = 2
输出: [1,2]
示例 2
输入: nums = [1],k = 1
输出: [1]

7.1 思路

  • 1、统计元素出现频率
    • 使用 map 来进行统计
  • 2、对频率进行排序
    • 使用优先级队列(priority_queue,容器适配器)
    • 优先级队列就是一个堆,因为优先级队列对外接口只是从队头取元素,从队尾添加元素,看起来就是一个队列,而且优先级队列内部元素是自动依照元素的权值排列
    • priority_queue 默认使用 max-heap(大顶堆)对元素排序,大顶堆是以 vector 为表现形式的完全二叉树
    • 堆是一棵完全二叉树,树中每个结点的值都不小于(或不大于)其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆,小于等于左右孩子就是小顶堆
    • 本题使用 min-heap(小顶堆),因为要统计最大前 k 个元素,只有小顶堆每次将最小的元素弹出,最后小顶堆里积累的才是前 k 个最大元素
  • 3、找出前 K 个高频元素
    • 流程如下图所示:图中的频率只有三个,所以正好构成一个大小为 3 的小顶堆,如果频率更多一些,则用这个小顶堆进行扫描
      在这里插入图片描述

7.2 代码实现

// 时间复杂度: O(nlogk)
// 空间复杂度: O(n)
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

class Solution {
public:
    // 小顶堆
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 要统计元素出现频率
        unordered_map<int, int> map; // map<nums[i],对应出现的次数>
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }

        // 对频率排序
        // 定义一个小顶堆,大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

        // 用固定大小为k的小顶堆,扫面所有频率的数值
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) { // 如果堆的大小大于了K,则队列弹出,保证堆的大小一直为k
                pri_que.pop();
            }
        }

        // 找出前K个高频元素,因为小顶堆先弹出的是最小的,所以倒序来输出到数组
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;

    }
};

int main() {
    Solution solution;
    vector<int> nums = {1, 1, 1, 2, 2, 3};
    int k = 2;
    vector<int> result = solution.topKFrequent(nums, k);
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
    cout << endl;
    return 0;
}
文章来源:https://blog.csdn.net/qq_42994487/article/details/135581877
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。