LeetCode 题解随笔：栈与队列

题解随笔：栈与队列"/>

LeetCode 题解随笔：栈与队列

目录

一、栈与队列基础知识

232.用栈实现队列

225. 用队列实现栈

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

二、栈的应用

20. 有效的括号

921. 使括号有效的最少添加

1541. 平衡括号字符串的最少插入次数

150. 逆波兰表达式求值

71. 简化路径

 三、队列的应用

239. 滑动窗口最大值

四、优先队列

347.前 K 个高频元素

1792. 最大平均通过率

---

一、栈与队列基础知识

232.用栈实现队列

class MyQueue {
public:MyQueue() {}void push(int x) {this->sIn.push(x);}int pop() {//sOut为先入元素，为空时将sIn内元素全部导入if (this->sOut.empty()) {while (!this->sIn.empty()) {this->sOut.push(this->sIn.top());this->sIn.pop();}}int res = this->sOut.top();this->sOut.pop();return res;}int peek() {int res = this->pop();this->push(res);return res;}bool empty() {return this->sIn.empty() && this->sOut.empty();}private:stack<int> sIn;stack<int> sOut;
};

利用两个栈实现，一个入队用，一个出队用。

注意两点：1.enpty()函数的简化写法；2.peek()函数复用了pop()函数，能使用代码复用的地方，尽量不要复制粘贴代码。

225. 用队列实现栈

class MyStack {
public:MyStack() {}void push(int x) {this->qMain.push(x);}int pop() {int size = this->qMain.size() - 1;//把队列1中的元素导入队列2，但保留最后一个元素while (size--) {this->qBackup.push(this->qMain.front());this->qMain.pop();}int res = this->qMain.front();this->qMain.pop();//把队列2拷贝给队列1，然后清空队列2this->qMain = this->qBackup;while (!this->qBackup.empty()) {this->qBackup.pop();}return res;}int top() {int res = this->pop();this->push(res);return res;}bool empty() {return this->qMain.empty();}private:queue<int> qMain;queue<int> qBackup;
};

用第二个队列作为第一个队列的备份，每次pop()时除最后一个元素外全部入队第二个队列。

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

string removeDuplicates(string s) {stack<char> filter;for (int i = s.size() - 1; i >= 0; i--) {if (filter.empty())  filter.push(s[i]);else if (s[i] == filter.top())  filter.pop();else  filter.push(s[i]);}string res;while (!filter.empty()) {res += filter.top();filter.pop();}return res;}

本题也可以将字符串作为栈，利用push_back和pop_back直接实现。 

---

二、栈的应用

20. 有效的括号

bool isValid(string s) {stack<char> rightRecord;for (auto i : s) {if (i == '(') rightRecord.push(')');else if (i == '{') rightRecord.push('}');else if (i == '[') rightRecord.push(']');//若需要输出左括号时，无该元素或无元素，说明不匹配或右括号多了else if (rightRecord.empty() || i != rightRecord.top()) return false;else rightRecord.pop();}//栈不为空，说明左括号多了return rightRecord.empty();}

不论括号是分段的，例如()[]{[]}有三段 ；还是括号只有囊括的，例如{[()]}只有一段。有效的字符串每一段对应的栈一定可以被清空。

另一个技巧是进栈右括号而非进栈左括号，这样只需要比较迭代元素i和栈顶元素是否一致即可。

借助本题的思路，可以完成如下题目：

921. 使括号有效的最少添加

    int minAddToMakeValid(string s) {int res = 0;int rightRecord = 0;for (auto i : s) {// 遇到左括号，记录需要的右括号数if (i == '(')   rightRecord++;// 遇到右括号时，需要右括号的栈空，说明右括号多了，需要添加左括号else if (rightRecord <= 0)    res++;else rightRecord--;}// 栈不为空，说明左括号多了，需要添加右括号return res + rightRecord;}

1541. 平衡括号字符串的最少插入次数

int minAddToMakeValid(string s) {int res = 0;int right_need = 0;for (int i = 0; i < s.size(); ++i) {// 遇到左括号，记录需要的右括号数if (s[i] == '(') {right_need += 2;}// 遇到右括号时，要保证右括号有连续两个else {// 需要一个左括号if (right_need == 0)    res++;else    right_need -= 2;// 满足连续性：跳过下一个右括号if (i + 1 < s.size() && s[i + 1] == ')') {i++;}// 不满足连续性：下一个不是右括号或者字符串结束，需要补一个右括号else {res++;}}}// 栈不为空，说明左括号多了，需要添加右括号return res + right_need;}

本题与上一题相比，关键在于出现右括号的处理，要保证每次出现的右括号是两个连续的右括号，否则要补一个右括号。 

150. 逆波兰表达式求值

    void GetTwoValues(stack<int>& s, int& tempA, int& tempB) {tempB = s.top();s.pop();tempA = s.top();s.pop();}int evalRPN(vector<string>& tokens) {stack<int> s;int tempA;int tempB;for (auto i : tokens) {if (i == "+") {GetTwoValues(s, tempA, tempB);s.push(tempA + tempB);}else if (i == "-") {GetTwoValues(s, tempA, tempB);s.push(tempA - tempB);}else if (i == "*") {GetTwoValues(s, tempA, tempB);s.push(tempA * tempB);}else if (i == "/") {GetTwoValues(s, tempA, tempB);s.push(tempA / tempB);}else {s.push(stoi(i));}}return s.top();}

后缀表达式适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。逆波兰表达式相当于是二叉树中的后序遍历。 

71. 简化路径

string simplifyPath(string path) {stack<char> simplePath;// 字符串末尾添加一个/用于处理最后一级目录path += '/';for (auto str : path) {// 每次遇到/时进行判断和操作if (str == '/' && !simplePath.empty()) {// 两个目录名之间必须只有一个斜杠 '/'if (simplePath.top() == '/') {while (!simplePath.empty() && simplePath.top() == '/') {simplePath.pop();}}else if (simplePath.top() == '.') {simplePath.pop();// 一个点（.）表示当前目录本身if (simplePath.top() == '/') {simplePath.pop();}// 两个点 （..） 表示将目录切换到上一级else if (simplePath.top() == '.') {simplePath.pop();// 需要返回上级目录的情况if (simplePath.top() == '/') {// 删除/..的/simplePath.pop();// 若存在上级目录，删除上级目录名以及/if (!simplePath.empty()) {while (simplePath.top() != '/') {simplePath.pop();}simplePath.pop();}}// 多个.表示的是文件名else {simplePath.push('.');simplePath.push('.');}}// 其余情况.也表示文件名else {simplePath.push('.');}}}simplePath.push(str);}// 最后一个目录名（如果存在）不能 以 '/' 结尾if (!simplePath.empty() && simplePath.top() == '/' && simplePath.size() != 1) {simplePath.pop();}string res;while (!simplePath.empty()) {res += simplePath.top();simplePath.pop();}reverse(res.begin(), res.end());return res;}

每种情况都考虑清楚即可。本题采用方式是遇到“/”时再进行处理。 

---

 三、队列的应用

239. 滑动窗口最大值

//用deque实现单调队列
class MyQueue {
public://滑动窗口第一个值等于队列最大值时才出队，否则不进行操作void pop(int value) {if (!this->m_queue.empty() && this->m_queue.front() == value) {this->m_queue.pop_front();}}//保持从头到尾由大到小void push(int value) {while (!this->m_queue.empty() && this->m_queue.back() < value) {this->m_queue.pop_back();}this->m_queue.push_back(value);}int front() {return this->m_queue.front();}
private:deque<int> m_queue;
};class Solution {
public: vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue mq;vector<int> res;//前k-1个元素进入单调队列for (int i = 0; i < k - 1; i++) {mq.push(nums[i]);}//从0到size()-k+1次循环，先入队（窗口内含k个元素），然后输出结果，再出队（窗口内含k-1个元素）for (int j = 0; j + k <= nums.size(); j++) {mq.push(nums[j + k - 1]);res.push_back(mq.front());mq.pop(nums[j]);}return res;}
};

本题采用单调队列这种数据结构来完成，一次循环的过程如下图所示（来源：代码随想录）：

单调队列的队头元素存放滑动窗口内元素的最大值，并且队列递减排列，保证队头元素始终是可能的最大值。这样从0到size()-k+1次循环中，每次输出myQueue.front()即可。

实现单调队列的递减排列，并不是要将滑动窗口中的全部元素递减排列，而是在入队的过程中，只保留可能的最大元素：从deque的队尾入队，当待入队元素大于当前队尾时，deque()从队尾不断出队。

但这样会导致队列中的元素不足k个，因此在实现myQueue的pop()操作时，需要判断num[i]是否等于当前队头，只有等于时才执行deque的pop()操作。

单调队列不是一成不变的，针对不同场景要开发不同的写法。

---

四、优先队列

347.前 K 个高频元素

class MyCompare {
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> freq;for (auto num : nums) {freq[num]++;}// 定义一个大小为k的小顶堆，用其扫描整个map// priority_queue<Type, Container, Functional>,Container为保存数据的容器priority_queue<pair<int, int>, vector<pair<int, int>>, MyCompare> priQueue;for (unordered_map<int, int>::iterator it = freq.begin(); it != freq.end(); it++) {priQueue.push(*it);// 元素数量大于k时，出队元素为最小元素if (priQueue.size() > k) {priQueue.pop();}}// 结果数组从大到小排列vector<int> res;for (int i = k - 1; i >= 0; i--) {res.push_back(priQueue.top().first);priQueue.pop();}return res;}
};

首先，可以很自然地想到用map来统计频率，由于不需要对键值排序，此处采用unorder_map。

要对map中的频率值排序，此处采用堆排序，实现方法是优先队列（小顶堆/大顶堆）。 

大顶堆：每个结点的值都大于或等于其左右孩子结点的值。
小顶堆：每个结点的值都小于或等于其左右孩子结点的值。
如果是排序，求升序用大顶堆，求降序用小顶堆。

而对于topK问题，最大的 K 个：小顶堆；最小的 K 个：大顶堆。因为只保留K个元素，而优先队列每次出队队头元素，若采用大顶堆，保留的是最小的K个元素；采用小顶堆则保留了最大的K个元素。利用仿函数可以改变优先队列的排序方式。

该算法的时间复杂度为O(nlog(k))，尤其注意排序过程中的时间复杂度为O(log(k))。

树结构和STL相关知识还要继续学习。

1792. 最大平均通过率

class Solution {
public:struct Ratio {int pass, total;bool operator < (const Ratio& oth) const {return (long long)(oth.total + 1) * oth.total * (total - pass) < (long long)(total + 1) * total * (oth.total - oth.pass);}};double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {priority_queue<Ratio> q;for (auto _class : classes) {q.push({ _class[0], _class[1] });}for (int i = 0; i < extraStudents; ++i) {auto ratio = q.top();q.pop();q.push({ ratio.pass + 1, ratio.total + 1 });}double pass_rate = 0;for (int i = 0; i < classes.size(); ++i) {auto ratio = q.top();pass_rate += (double) ratio.pass / ratio.total;q.pop();}return pass_rate / classes.size();}
};

利用优先队列，每次选择通过率增加量最大的班级，加入extraStudents即可。

本题需要注意以下几点：

1. 整型和浮点数之间的转换。如果不转化为浮点数，整型相除结果为0；
2. priority_queue存储的是struct，而非vector<int>，可以减小vector创建的开销。否则会超出时间限制；
3. priority_queue的定义：第三个元素要传入类型名（是在进行类型声明，而非直接传入谓词），可以使用decltype(cmp)来结合lambda表达式。

谓词包括：函数谓词、函数指针谓词、Lambda表达式谓词、函数对象谓词和库定义的函数对象谓词。