题目一览图
零、队栈概述
【队栈】都属于被限制的线性表，主要限制是在增删的位置。
- 【栈】只能在尾结点增删 - 后入先出（LIFO Last in First out）
- 【队】在尾结点增，在头结点删 - 先入先出（FIFO First in First out）
一、基本问题
类型概述**
题型一 | 栈
题型串联
- 【用栈实现队列】考察的是对栈的基本理解，所以作为本题型的第一题。
- 【删除字符串中的所有相邻重复项】和【**有效的括号】**都是基本匹配题，不论是相同元素的匹配还是左右括号的匹配。
- 【逆波兰表达式求值】和【简化路径】也可以认为是一种匹配，遇到特定符号进行的相邻串操作。【逆波兰表达式求值】是匹配到【运算符号】，将其和前两个数字合并；【简化路径】是匹配
../，和前一个路径合并。 【**最长有效括号**】这是建立在【有效的括号】的基础上的题目，除了基本的栈操作，还要引入贪心算法。
1 用栈实现队列
【概述】栈问题
【题目描述**】**
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：void push(int x)将元素x推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回 true ；否则，返回 false
【题目示例**】**
输入：["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 1myQueue.pop(); // return 1, queue is [2]myQueue.empty(); // return false
【题目分析**】**
本题要求用栈实现队。本题考查对队和栈的理解程度，栈是先入后出，队是先入先出，那怎么转换那？使用两个栈即可。所以具体代码流程如下：
- 设置两个属性
stkIn和stkOut,分别作为【进入栈】和【出来栈】。 - 【压入 push】压入元素的时候进入【进入栈】，作为缓存。
- 【弹出 pop】弹出有两种情况：
stkOut为空的时候，说明之前没翻转。所以将stkIn元素依次压入stkOut，实现元素的翻转。stkOut不为空的时候，翻转后的元素还没完全弹出，直接弹出stkOut。
- 【栈顶 peek】直接弹出元素，再放回去就行。
- 【空 empty】两个栈全为空即可。
var MyQueue = function() {
this.stkIn = [];
this.stkOut = [];
};
MyQueue.prototype.push = function(x) {
this.stkIn.push(x);
};
MyQueue.prototype.pop = function() {
if(!this.stkOut.length){
while(this.stkIn.length) this.stkOut.push(this.stkIn.pop());
}
return this.stkOut.pop();
};
MyQueue.prototype.peek = function() {
const tmp = this.pop();
this.stkOut.push(tmp);
return tmp;
};
MyQueue.prototype.empty = function() {
return !this.stkIn.length && !this.stkOut.length;
};
2 删除字符串中的所有相邻重复项
【概述】栈问题
【题目描述**】**
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
【题目示例**】**
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
【题目分析**】**
本题要求删除相邻的重复项。总体来说，本题可以看做消消乐，相邻元素被消除。所以具体代码流程如下：
对比栈顶元素和当前元素，
- 【相同】说明是相邻重复元素，相互抵消，即出栈。
- 【不相同】说明不是相邻重复元素，入栈。
var isValid = function(s) { const stk = []; for(let c of s){ if( c === '(' || c === '{' || c === '[') stk.unshift(c); else{ if( stk.length && Math.abs(stk[0].charCodeAt()-c.charCodeAt())<=2) stk.shift(); else return false; } } return stk.length === 0; };3 有效的括号
【概述】栈问题
【题目描述**】**
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
【题目示例**】**
输入: "()"
输出: true
【题目分析**】**
本题要求判断字符串是否为有效的括号。总体来说就是根据规则办事，由于右括号需要跟最近的左括号匹配，也就是说跟上一个最晚出现的括号匹配，符合栈的性质，后入先出。所以具体代码流程如下：
- 遇到【左括号】将其入栈，进入等待区，等待匹配。
- 遇到【右括号】分为以下几种情况：
- 【空栈】说明等待区无人，没人跟【右括号】匹配，判定为非法。
- 【栈顶元素不匹配】说明看不上眼，直接宣告失败。
- 【栈顶元素匹配】合适，通过。
- PS：可以利用左右括号 ASCII 相近的特性，化简代码。
var isValid = function(s) {
const stk = [];
for(let c of s){
if( c === '(' || c === '{' || c === '[') stk.unshift(c);
else{
if( stk.length && Math.abs(stk[0].charCodeAt()-c.charCodeAt())<=2) stk.shift();
else return false;
}
}
return stk.length === 0;
};
4 最长有效括号
【概述】栈问题
【题目描述**】
给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
【题目示例**】
输入: "()"
输出: true输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
【题目分析**】
本题要求得到有效的括号的最大长度。遇到这种问法，就知道要用一些算法了。本题可用动态规划或者贪心算法，为了利用栈的特性，我们采用贪心算法来处理问题。
【贪心算法】**的基本思路是：
- 设置栈
stk用于存储【左括号】，res记录最大长度。 - 设置索引
i和start，前者用于遍历字符串，后者用于记录【合法串的初始位置】。 - 【合法串的初始位置】更新条件是当前元素破坏了括号的有效性，即【右括号】多于【左括号】，栈为空。
【最大长度】更新有两种情况：
- 弹出一个【左括号】后，栈为空。说明从
start到当前已经没有可匹配的【左括号】了，所以从start到当前都合法，更新最大长度Math.max(res,i-start)。 - 弹出一个【左括号】后，栈不为空。说明从
start到当前还有可匹配的【左括号】，但是我们并不能确定它们真的可以被匹配，所以更新最大长度Math.max(res,i-stk[stk.length-1])。 ```javascript var longestValidParentheses = function(s) { const stk = []; let res = 0;
for(let i = 0 , start = -1 ; i < s.length ; i++){ if(s[i]===’(‘) stk.push(i); else{
if( stk.length > 0){ stk.pop(); if( stk.length > 0 ) res = Math.max(res,i-stk[stk.length-1]); else res = Math.max(res,i-start); }else start = i ;} } return res; };
<a name="BYfYK"></a> #### 5 [逆波兰表达式求值](https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/) **【概述】栈问题**<br />**【题目描述****】**<br />根据[ 逆波兰表示法](https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437)，求表达式的值。有效的运算符包括 `+`, `-`, `*`, `/` 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。<br />**【题目示例****】**输入: [“2”, “1”, “+”, “3”, ““] 输出: 9 解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) 3) = 9
`` **【题目分析****】**<br />本题要求根据逆波兰表达式计算式子。首先要了解逆波兰表达式的含义，即每次遇到计算符号，就计算前两个数的值，如[ 3 , 2 , 1 , + , ], 相当于遇到+计算1+2=3，遇到，就计算3*3 = 9`。所以基本思路就有了，遇到数字压入栈，遇到符号提取前两个数字计算，并将结果再次压入栈。具体流程如下：- 弹出一个【左括号】后，栈为空。说明从
设置栈
stk用于存储【数字】，设置索引c遍历字符串。- 【遇到数字】直接压入栈（注意是字符串，需要转化到数字）。
【遇到符号】执行以下操作：
- 从栈弹出两个数字，即前两位
a和b。 - 将计算结果压入栈。
var evalRPN = function(tokens) { const stk = []; for( let c of tokens){ if( c === '+' || c === '-' || c === '*' || c === '/'){ const a = stk.pop() , b = stk.pop(); if( c === '+') stk.push(a+b); else if( c === '-' ) stk.push(b-a); else if( c === '*' ) stk.push(a*b); else if( c === '/' ) stk.push(parseInt(b/a)); } else stk.push(c-'0'); } return stk.pop(); };6 简化路径
【概述】栈问题
【题目描述**】
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径。请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
【题目示例**】
【题目分析**】**输入："/home/" 输出："/home" 解释：注意，最后一个目录名后面没有斜杠。
本题要求根据规则简化路径。其中../的操作，符合出栈操作，所以我们可以利用这一点实现简化。一种简单的方法是，现将路径字符串按照/分割，进而得到一个路径数组，然后配合栈把返回上一层的路径处理了。 具体流程如下：
- 从栈弹出两个数字，即前两位
先将路径字符串以
/分割，得到【路径数组】- 设置栈
stk用于存储【路径字符串】，设置索引c遍历【路径数组】。- 【遇到
**''****'.'**】直接跳过，不放入stk。 - 【遇到
**../**】弹出stk顶层路径。 - 【其他】都默认为有效路径，压入
stk。
- 【遇到
- 最后将
stk的路径以/连接。var simplifyPath = function(path) { const tmpPath = path.split('/') , res = []; for( let c of tmpPath ){ if( c === '' || c==='.') continue; if( c === '..') res.pop(); else res.push(c); } return '/'+res.join('/'); };二、单调队/栈
类型概述
【单调队栈】就是内部具有单调性，需要增加额外的操作维护单调性。
【单调栈】分为单调递增栈和单调递减栈，
- 基本操作：
- 【新元素 > 栈顶】入栈。
- 【新元素 < 栈顶】弹出栈顶元素，直至栈顶小于新元素。
- 特性：
- 栈内元素单调。
- 当元素出栈时，说明它【大于新元素】，也【大于出栈完成后的栈顶】，理解为峰值。
- 代码模板
const stk = []; for( let i = 0 ; i < nums.length ; i++ ){ while( !stk.length && stk[stk.length-1] > nums[i] ) stk.pop(); stk.push(nums[i]); }
题型一 | 单调栈
题型串联
1 柱状图中最大的矩形
【概述】单调栈
【题目描述**】
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
【题目示例**】
输入: [2,1,5,6,2,3]
输出: 10
【题目分析**】**
本题要求找出柱状图最大矩形。为了得到最大面积，我们使用的【单调栈】【弹出元素】同时大于【当前元素】和【单调栈前一个元素】，并且同时在【当前元素】和【单调栈前一个元素】之间没有小于【弹出元素】这个特点。所以说每次弹出元素时，我们获取【当前元素】和【单调栈前一个元素】的索引，可以得到以【弹出元素】为高的最大矩阵。具体操作为：
- 设置栈
stk作为单调栈，res记录最大长度。设置索引i遍历heights。 - 给
heights增加边界，即左右插入0。 - 如果【栈顶元素】大于当前高度
heights[i]，说明要弹出元素了，开始一系列操作：- 得到【弹出元素】，设置为
cur。 - 得到【当前元素】索引，设置为
r = i - 1。 - 得到【单调栈前一个元素】索引，设置为
l=``stk[stk.length-1] + 1。 - 计算当前面积最大值，
(r-l+1)*heights[cur]并更新res。
- 得到【弹出元素】，设置为
- 如果不是将
heights[i]压入栈。
var largestRectangleArea = function(heights) {
const n = heights.length , stk = [];
let res = 0;
heights.unshift(0),heights.push(0);
for( let i = 0 ; i < heights.length ; i++){
while( stk.length && heights[stk[stk.length-1]] > heights[i]) {
const cur = stk.pop();
const l = stk[stk.length-1] + 1 , r = i - 1 ;
res = Math.max(res,(r-l+1)*heights[cur]);
}
stk.push(i);
}
return res;
};
2 最大矩形
【概述】单调栈
【题目描述**】
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
【题目示例**】
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
【题目分析**】**
本题要求计算二维矩阵里的最大矩形。初看不太见过，但是仔细看可以发现其实就是【柱状图中最大的矩形】演变。 那如何变成【柱状图中最大的矩形】？
- 设置数组
heights存储【以不同行为底的矩形高度】。设置索引ij遍历matrix每行每列。 - 遍历每一行，将
i行作为底，再判断ij位置是否为1：- 【是 1 】说明当前行直接连着带
1的矩形 ，高度加一heights[j] += 1。 - 【是 0 】说明当前行不直接连着带
1的矩形，直接清零，heights[j] += 0。
- 【是 1 】说明当前行直接连着带
- 一行遍历完之后，将会得到以
i行为底的矩行高heights，至此完成转化。
var maximalRectangle = function(matrix) {
if( !matrix.length || !matrix[0].length ) return 0 ;
const n = matrix.length , m = matrix[0].length;
let res = 0;
const largestRectangleArea = function(heights) {
const n = heights.length , stk = [];
heights.unshift(0),heights.push(0);
for( let i = 0 ; i < heights.length ; i++){
while( stk.length && heights[stk[stk.length-1]] > heights[i]) {
const cur = stk.pop();
const l = stk[stk.length-1] + 1 , r = i - 1 ;
res = Math.max(res,(r-l+1)*heights[cur]);
}
stk.push(i);
}
};
let heights = new Array(m).fill(0);
for(let i = 0; i < n;i++){
for(let j = 0;j < m;j++){
if(matrix[i][j] == '1'){
heights[j] += 1;
}else{
heights[j] = 0;
}
}
largestRectangleArea([...heights]);
}
return res;
};
3 接雨水
【概述】栈问题
【题目描述**】
给定 _n_ 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
【题目示例**】
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
【题目分析**】**
本题要求计算凹槽可以接多少雨水。与【柱状图中最大的矩形】不同，这次找的是凹槽，所以我们用的是递减栈。也就是当【当前元素】大于【栈顶元素】时，将会弹出元素，说明可以接雨水了，有以下几个步骤：
- 栈里面有一堆和【弹出元素】一边大的柱子，这是我们要扩大凹槽的长度，直到【栈顶元素】大于【当前元素】。
- 此时【弹出元素】在【栈顶元素】和【当前元素】之间形成凹槽，面积就是【栈顶元素】和【当前元素】的最小值乘以【弹出元素】横跨的距离。
var trap = function(height) { if(!height.length) return 0; const stk = []; let res = 0; for( let i = 0 ; i < height.length ; i++){ while( stk.length && height[stk[stk.length-1]] < height[i] ){ let cur = stk.pop(); while( stk.length && height[stk[stk.length-1]] === height[cur]) stk.pop(); if(stk.length){ let top = stk[stk.length-1]; res += (Math.min(height[top],height[i]) - height[cur]) * (i - top - 1) } } stk.push(i); } return res; };三、优先队列
类型概述**
【优先队列】本质是【堆】，虽然从外部接口来看，无非是从队头取元素，从队尾添加元素，但是玄机在队列内部。优先级队列内部元素是通过【大顶堆】自动实现依照元素的权值排列。
题型串联
1 合并K个升序链表
【概述】优先队列
【题目描述**】
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
【题目示例**】
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
【题目分析**】**
本题要求合并K个优先队列。本题就是将 K 个链表的节点纷纷放入【优先队列】维护节点们的单调性，然后依次输出连接即可。本题唯一的关键就是【优先队列的实现】，并且将传统代码修改为维护节点的优先队列。
function pQueue (){
const queue = [];
this.enqueue = (node)=>{
if(this.empty()) queue.push(node);
else{
let flag = true;
for(let i = 0 ; i < queue.length ; i++){
if(node.val<queue[i].val) {
queue.splice(i,0,node),flag = false;
break;
}
}
if(flag) queue.push(node);
}
}
this.dequeue = ()=>queue.shift();
this.size = ()=>queue.length;
this.empty = ()=>queue.length === 0;
this.front = ()=>queue[0];
}
var mergeKLists = function(lists) {
const pQ = new pQueue() , dummy = new ListNode();
for(let list of lists) if(list) pQ.enqueue(list);
let p = dummy;
while(!pQ.empty()){
let tempNode = pQ.dequeue();
if(tempNode.next) pQ.enqueue(tempNode.next);
p = p.next = tempNode;
}
return dummy.next;
};
若有收获，就点个赞吧
0 人点赞
