本章记录一些有关栈和队列的一些较为经典或者自己第一次做印象比较深刻的算法以及题型，包含自己作为初学者第一次碰到题目时想到的思路以及网上其他更优秀的思路，本章持续更新中......
目录
No 232. 用栈实现队列(简单)
No 20. 有效的括号(简单)
No 150. 逆波兰表达式求值 (中等)
No 347.前 K 个高频元素（中等）
No 239. 滑动窗口最大值（困难）
No 232. 用栈实现队列(简单)
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-queue-using-stacks/
题目描述：
请你仅使用两个栈实现先入先出队列。
队列应当支持一般队列支持的所有 *** 作（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（双端队列）来模拟一个栈，只要是标准的栈 *** 作即可。
输入：
["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思路：这个题目的实际意义不大，仅仅是为了考察对于栈和队列的理解和基本 *** 作。
要用栈是后进先出，队列是先进先出，所以要用栈实现队列，我们用两个栈就可以了。
具体 *** 作是我们首先把stack1当中的数据压入stack2中，然后将stack2中的栈顶元素出栈，再将stack2中的数据压回stack1，这样就模拟了队列中先进先出的效果。
还有一个题目是用队列实现栈，也是类似的思路，用两个队列。
先将queue1中除了队尾数据以外的其他数据加入队列queue2中，然后将queue1中的数据d出，再将queue2中的数据加入到队列queue1中，就模拟了栈的后进先出效果。
class MyQueue {
public:
stack stackIn;
stack stackOut;
MyQueue() {
}
void push(int x) {
stackIn.push(x);
}
int pop() {
//将In的数据压入Out，此时Out的栈顶就是In的栈底
if(stackOut.empty()){
while(!stackIn.empty()){
//将stackIn全部压入stackOut
stackOut.push(stackIn.top());
//将stackIn中的数据出栈
stackIn.pop();
}
}
//此时stackOut中栈顶的数据就是stackIn中栈底的数据，将stackOut中栈顶数据出栈，就实现了队列 *** 作
int res=stackOut.top();
stackOut.pop();
return res;
}
int peek() {
int res=this->pop();
//因为pop *** 作将resd出了，而peek不需要d出，所以需要压回去
stackOut.push(res);
return res;
}
bool empty() {
return stackIn.empty()&&stackOut.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/ 来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses/
题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true思路：括号匹配是栈的经典题目。
这个题目我们进行分类讨论即可。
括号字符串无效的情况只有两大类，括号多余和括号不匹配。
其中括号多余又可以分为左边的多余和右边的多余。
所以一共是三种情况：1、左边括号多余；2、右边括号多余；3、括号不匹配。
我们首先将遍历到的每一个左括号的另一半压入栈中，这样将来匹配到对应的括号可以直接用==来判断。
在匹配过程中：
1、如果当前的括号和栈顶括号相同，那么这是一对括号，进行出栈 *** 作。
如果还没有遍历完，栈就已经空了，那么说明此时一定是右边的括号多余了，因为只有遍历到的符号是左括号才将对应的右括号压栈，如果没遍历完就空栈了，剩下的一定是右括号。
2、如果遍历过程中，栈不为空，且当前遍历到的元素不等于栈顶元素(能够走到这一步的一定是右括号，因为如果是左括号的话就把对应的右括号压栈了)，那么就是括号不匹配的情况。
虽然可能两个括号中间还会有其他括号，但中间括号理论上是成对的，那么都是会出栈的；如果不成对，那么也对应的是2这种情况。
此时遍历到的括号一定和左括号匹配，否则就不是一对括号。
3、如果都便利完了，但是栈不是空栈，说明有左边的括号剩下了。
因为只有遍历到左括号的时候才会压栈，此时栈不为空，那就是左括号剩下了。
class Solution {
public:
bool isValid(string s) {
stack res;
int Slen=s.size();
for(int i=0;i
这里可以用 != 来判断是因为入栈的时候就是把对应的匹配括号入栈的。
else if(s[i]!=res.top()){
return false;
}
//当栈顶元素和当前括号匹配时，就把这个元素出栈
else{
res.pop();
}
}
//匹配结束时还不为空那么就不匹配
return res.empty();
}
};
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation
题目描述：
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。
每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。
换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 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可以体会一下。
中缀表达式不利于我们阅读，但是方便计算机计算，后缀表达式不需要括号就可以正确的按照运算符的优先级进行计算。
这题的思路就是把遍历的数字都入栈，当遍历到运算符的时候就取出两个数字进行计算，需要注意使用的是栈，先出栈的数字是在运算符后面的，后出栈的数字是在运算符前面的，要注意两个数字的相对与运算符的位置关系。
将计算的结果压入栈中，参与下一轮计算，最后栈顶的数字就是最终计算的结果。
class Solution {
public:
int evalRPN(vector& tokens) {
stack number;
int len=tokens.size();
for(int i=0;i 来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-elements/
题目描述：
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。
你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]思路：本题最开始是想到用哈希map来做的，因为涉及到对出现次数进行计数。
最初想到的将出现次数作为 key，将数值作为value，因为毕竟是要找到出现次数最多的数值嘛，且次数有可能重复，所以综合考虑了一下想使用 multimap ，但是实现的过程中发现，multimap 不提供下标运算(does not provide a subscript operator)，所以只能考虑如何使用unordered_map实现。
使用unordered_map的话，就不能把次数作为 key 了，因为key不可重复，只能把数值作为 key，出现次数作为 value。
这样的话新的问题就出现了，我想根据value进行排序，但是unordered_map没有这种 *** 作。
这时想起了 pair 模板类型，pair 可以用可以 first 和 second 访问 pair 中的两个数值。
将unordered_map转移到 pair 中，然后再使用sort 按照 pair 中的 second 值，也就是 unordered_map 的 value 值进行排序来。
排序后前 K 个 pair 的 first 就是要找的答案。
map方法：
class Solution {
public:
//map方法
static int cmp(pair a, pair b){
//按照value排序
return a.second>b.second;
}
vector topKFrequent(vector& nums, int k) {
/*map方法*/
//key为数值，value为次数
unordered_map map_count;
int nums_len=nums.size();
for(int i:nums){
map_count[i]++;
}
//把unordered_map转变为pair便于排序
vector> temp;
for(auto it=map_count.begin();it!=map_count.end();it++){
temp.push_back(pair(it->first,it->second));
}
//对value按照降序排序
sort(temp.begin(),temp.end(),cmp);
//获取结果
vector res;
for(int i=0;i 还有一种方法是使用优先级队列，这个优先级队列使用堆来实现。
这里简单介绍一下堆这个数据结构。
堆是一个完全二叉树，可以分为小顶堆和大顶堆。
小顶堆就是父亲节点总是小于等于两个子节点，大顶堆就是父亲节点总是大于等于两个子节点。
而在堆中，移出堆的元素总是堆顶元素。
这里我们用小顶堆来实现，为什么不用大顶堆呢，不是要找出现次数最高的K个元素嘛。
这里还要结合大小顶堆的特点来看。
大顶堆总是将堆顶的最大元素首先移出，用大顶堆没办法保存最大的元素，小顶堆反之。
所以这里用小顶堆是更好的选择。
而且我们可以只维护大小为K的小顶堆，因为小顶堆总是将堆顶最小的元素最先移出，所以当遍历完之后，小顶堆中剩下的 K 个元素不就是出现次数最多的 K个元素吗？所以，综上所述，我们用小顶堆实现优先级队列。
首先将数值的出现次数记录到unordered_map中，然后把unordered_map push 到小顶堆实现的优先级队列中，push的过程中，每当堆的元素大于K，就把堆顶的元素移出。
这样最后堆中剩下的K个就是要找的答案。
优先级队列方法：用小顶堆实现
class Solution {
public:
/*堆方法*/
class comp{
public:
bool operator()(const pair& left, const pair& right){
return left.second>right.second;
}
};
vector topKFrequent(vector& nums, int k) {
unordered_map map_count;
int nums_len=nums.size();
//记录到map中
for(int i=0;i:Type 就是数据类型,Container 就是容器类型,Functional 就是比较的方式
priority_queue,vector>,comp> pri_queue;
for(auto it=map_count.begin();it!=map_count.end();it++){
//加入到堆中，加入的时候就排序了
pri_queue.push(*it);
//堆中的元素数量大于k了，就d出，d出的时候是d出的上面的小的元素
if(pri_queue.size()>k){
pri_queue.pop();
}
}
//把前K个元素取到vector中, 注意是倒序
vector res(k);
for(int i=k-1;i>=0;i--){
res[i]=pri_queue.top().first;
pri_queue.pop();
}
return res;
}
}; 来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum
题目描述：
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。
滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]思路：这个题目拿到手一看，好像不是很难呀，为什么是困难题。
所以按照自己最开始的思路往下做，做完了发现，测试样例能通过，一提交发现超时，这才明白困难的点在这里。
实在没有其他思路，所以就去看了下应该用什么数据结构，然后再自己去做。
提示使用单调队列来做这个题目。
单调队列就是维护一个拍好序的队列，队列的头是最大或者最小的元素。
如果将窗口的数字都放入队列，然后进行排序，那和我之前的思路区别不大，肯定会超时，所以肯定有其他思路。
仔细观察可以发现，其实不用每次都对窗口中的数字排序，而且也不用都放到队列里在进行排序，我们可以利用单调队列的双向性，在窗口中的数字要加入单调队列的时候进行判断，通过这个限制条件，使得进入单调队列的数字都符合单调队列的特点。
具体要求怎么实现呢？在窗口内的数字进入单调队列的时候，我们可以要求所有进入单调队列的数字必须小于等于队列尾的元素，如果不符合条件，那就将队尾的元素d出，直到符合条件在加入队尾。
当窗口中所有的数字都按照这种规则加入单调队列后，此时单调队列的头就是当前窗口的最大值。
下一步就要进行窗口的移动 *** 作了，窗口的移动 *** 作会导致单调队列的变化，会进行下一轮的push *** 作。
但是在进行push *** 作之前，我们得考虑单调队列里的有些数字是不是已经不在窗口内了。
因为此时单调队列头部的元素不一定就是窗口的头部数字，所以只有当窗口头部的数字==单调队列的头部数字的时候，才将单调队列的头部d出。
否则不 *** 作。
class Solution {
public:
//自定义单调队列，底层实现为deque
class MyQueue{
public:
deque windowsQue;
//队列出口的值等于数组中的值时才d出,否则队列不d出
void myPop(int value){
if(!windowsQue.empty() && value == windowsQue.front()){
windowsQue.pop_front();
}
}
//进入单调队列的数字都是小于等于入口处的数字的，如果要进入队列的数值大于入口处的值，则将入口处的值d出，再进行比较，直到要进入队列的值小于等于入口处的值。
这样做是保证队列中的front处为最大值。
每一轮进行的push *** 作次数是窗口的大小。
void myPush(int value){
while(!windowsQue.empty() && value>windowsQue.back()){
windowsQue.pop_back();
}
//当把大于value的队列中的数字都d出时，在进入队列
windowsQue.push_back(value);
}
//此时窗口中的出口处，也就是front处的值就是最大值
int getMaxValue(){
return windowsQue.front();
}
};
vector maxSlidingWindow(vector& nums, int k) {
//获取单调队列
MyQueue windowsQue;
vector res;
int nums_len=nums.size();
//先将前K个元素放进单调队列中，注意这里的push方法是自定义的
for(int i=0;i maxSlidingWindow(vector& nums, int k) {
// //结果正确，但是超时，时间复杂度太高
// int nums_len=nums.size();
// vector res;
// //首先处理特殊情况
// if(nums_len(nums[nums_len-1]);
// }
// }
// //一般情况
// else{
// for(int i=0;i windows(k);
// int sign_windows=0;
// for(int j=i;j
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）