AI summary
type
status
date
slug
summary
category
tags
icon
password

考察先进后出性质

对于栈这种数据结构的考察，主要考察先进后出特点的运用，比如表达式运算、括号合法性检测等问题，下面列出几个使用栈的经典场景。

71. 简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。
请注意，返回的 规范路径 必须遵循下述格式：
  • 始终以斜杠 '/' 开头。
  • 两个目录名之间必须只有一个斜杠 '/' 。
  • 最后一个目录名（如果存在）不能 以 '/' 结尾。
  • 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
返回简化后得到的 规范路径 。
这题比较简单，利用栈先进后出的特性处理上级目录 ..，最后组装化简后的路径即可。
函数思维：如果不让用 split，那么你可以单独实现一个自己的 split 函数，而不是把逻辑和算法题混在一起，这样会清晰一些。

143. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
这题的难点在于：一个单链表只能从头部向尾部遍历节点，无法从尾部开始向头部遍历节点。
那么我们可以利用「栈」先进后出的结构特点，按从头到尾的顺序让链表节点入栈，那么出栈顺序就是反过来从尾到头了。
注意在最后不要忘了切断原来的链接：cur.next = None ，防止成环。

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
  1. 左括号必须用相同类型的右括号闭合。
  1. 左括号必须以正确的顺序闭合。
  1. 每个右括号都有一个对应的相同类型的左括号。
栈是一种先进后出的数据结构，处理括号问题的时候尤其有用。
括号的有效性判断在笔试中和现实中都很常见，比如说我们写的代码，编辑器会检查括号是否正确闭合。而且我们的代码可能会包含三种括号 [](){}，判断起来有一点难度。
解决这个问题之前，我们先降低难度，思考一下，如果只有一种括号 ()，应该如何判断字符串组成的括号是否有效呢？
假设字符串中只有圆括号，如果想让括号字符串有效，那么必须做到：
每个右括号 ) 的左边必须有一个左括号 ( 和它匹配。
比如说字符串 ()))(( 中，中间的两个右括号左边就没有左括号匹配，所以这个括号组合是无效的。
那么根据这个思路，我们可以写出算法：
如果只有圆括号，这样就能正确判断有效性。对于三种括号的情况，我一开始想模仿这个思路，定义三个变量 left1，left2，left3 分别处理每种括号，虽然要多写不少 if else 分支，但是似乎可以解决问题。
但实际上直接照搬这种思路是不行的，比如说只有一个括号的情况下 (()) 是有效的，但是多种括号的情况下， [(]) 显然是无效的。
仅仅记录每种左括号出现的次数已经不能做出正确判断了，我们要加大存储的信息量，可以利用栈来模仿类似的思路。
我们这道题就用一个名为 left 的栈代替之前思路中的 left 变量，遇到左括号就入栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配。

150. 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。
提示：
  • 1 <= tokens.length <= 104
  • tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数
首先看一下逆波兰表达式怎么算的。
逆波兰表达式发明出来就是为了方便计算机运用「栈」进行表达式运算的，其运算规则如下：
按顺序遍历逆波兰表达式中的字符，如果是数字，则放入栈；如果是运算符，则将栈顶的两个元素拿出来进行运算，再将结果放入栈。对于减法和除法，运算顺序别搞反了，栈顶第二个数是被除（减）数。
所以这题很简单，直接按照运算规则借助栈计算表达式结果即可。
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
  • 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
  • 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
  • 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
  • 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
向零截断：int(a/b)

388. 文件的最长绝对路径

假设有一个同时存储文件和目录的文件系统。
这里将 dir 作为根目录中的唯一目录。dir 包含两个子目录 subdir1 和 subdir2 。subdir1 包含文件 file1.ext 和子目录 subsubdir1；subdir2 包含子目录 subsubdir2，该子目录下包含文件 file2.ext 。
在文本格式中，如下所示(⟶表示制表符)：
如果是代码表示，上面的文件系统可以写为 "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" 。'\n' 和 '\t' 分别是换行符和制表符。
文件系统中的每个文件和文件夹都有一个唯一的 绝对路径 ，即必须打开才能到达文件/目录所在位置的目录顺序，所有路径用 '/' 连接。上面例子中，指向 file2.ext 的 绝对路径 是 "dir/subdir2/subsubdir2/file2.ext" 。每个目录名由字母、数字和/或空格组成，每个文件名遵循 name.extension 的格式，其中 name 和 extension由字母、数字和/或空格组成。
给定一个以上述格式表示文件系统的字符串 input ，返回文件系统中 指向 文件 的 最长绝对路径 的长度 。 如果系统中没有文件，返回 0。
我觉得这道题还是比较实用的，因为在我做这道题之前，我就思考并解决过这个问题，可以在这里和大家分享下我的使用场景：
你可以看我的 GitHub 仓库中的文章目录，是通过缩进来表示层级的，很类似本题所说的场景。然而我需要把这些目录转化成 HTML 文档，按照文件目录的形式把这些 HTML 部署到 我的网站 上。你看，这是不是就涉及到本题生成文件的绝对路径的问题？
可以用栈来辅助，对于每一个路径，都去维护正确的父路径，从而计算最长路径的长度。具体看代码注释吧。
当然，题目只要求计算长度，所以 stk 可以只记录长度。
注意，对于例子：input = "file1.txt\nfile2.txt\nlongfile.txt" ，需要考虑 '/' if stk else '' 。

栈的设计题

除了上面几道题，还有一类常考题目是让你设计具备额外功能的栈结构。

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。
我们知道栈是一种操作受限的数据结构，只能从栈顶插入或弹出元素，所以对于标准的栈来说，如果想实现本题的 getMin 方法，只能老老实实把所有元素弹出来然后找最小值。想提高时间效率，那肯定要通过空间换时间的思路。
不过在具体说解法之前，我想聊一下动态集合中维护最值的问题。这类问题看似简单，但实际上是个很棘手的问题。其实本题就是如下一个场景：
假设你有若干数字，你用一个 min 变量维护了其中的最小值，如果现在给这些数字中添加一个新数字，那么只要比较这个新数字和 min 的大小就可以得出最新的最小值。但如果现在从这些数字钟删除一个数字，你还能用 min 变量得到最小值吗？答案是不能，因为如果这个被删除的数字恰好是最小值，那么新的 min 变量应该更新为第二小的元素对吧，但是我没有记录第二小的元素是多少，所以只能把所有数字重新遍历一遍。
明确了难点再回到本题，就可以对症下药了。删除栈顶元素的时候，不确定新的最小值是多少，但楼下那哥们知道啊，他当时入栈时的最小值，就是现在的最小值呗。
所以这道题的关键就是，每个元素入栈时，还要记下来当前栈中的最小值。比方说，可以用一个额外的栈 minStk 来记录栈中每个元素入栈时的栈中的最小元素是多少，这样每次删除元素时就能快速得到剩余栈中的最小元素了。

895. 最大频率栈

设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。
实现 FreqStack 类:
  • FreqStack() 构造一个空的堆栈。
  • void push(int val) 将一个整数 val 压入栈顶。
  • int pop() 删除并返回堆栈中出现频率最高的元素。
    • 如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。
这种设计数据结构的问题，主要是要搞清楚问题的难点在哪里，然后结合各种基本数据结构的特性，高效实现题目要求的 API。
那么，我们仔细思考一下 push 和 pop 方法，难点如下：
  1. 每次 pop 时，必须要知道频率最高的元素是什么。
  1. 如果频率最高的元素有多个，还得知道哪个是最近 push 进来的元素是哪个。
为了实现上述难点，我们要做到以下几点：
  1. 肯定要有一个变量 maxFreq 记录当前栈中最高的频率是多少。
  1. 我们得知道一个频率 freq 对应的元素有哪些，且这些元素要有时间顺序。
  1. 随着 pop 的调用，每个 val 对应的频率会变化，所以还得维持一个映射记录每个 val 对应的 freq。
实际上就是每个 freq 对应一个栈，相同的值存储在不同的栈里，由于栈的后进先出性质，天然的就知道最近 push 进来的元素是哪个。
算法执行过程如下：
notion image
完整代码如下，要记住在 push 和 pop 方法中同时修改 maxFreq、VF 表、FV 表，否则容易出现 bug。

括号问题延伸

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

只有满足下面几点之一，括号字符串才是有效的：
  • 它是一个空字符串，或者
  • 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
  • 它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串 s ，在每一次操作中，你都可以在字符串的任何位置插入一个括号
  • 例如，如果 s = "()))" ，你可以插入一个开始括号为 "(()))" 或结束括号为 "())))" 。
返回 为使结果字符串 s 有效而必须添加的最少括号数。
核心思路是以左括号为基准，通过维护对右括号的需求数 need，来计算最小的插入次数。
需要注意：算法为什么返回 res + need？
因为 res 记录的左括号的插入次数，need 记录了右括号的需求，当 for 循环结束后，若 need 不为 0，那么就意味着右括号还不够，需要插入。
比如说 s = "))(" 这种情况，插入 2 个左括号之后，还要再插入 1 个右括号，使得 s 变成 "()()()"，才是一个有效括号串。

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

给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：
  • 任何左括号 '(' 必须对应两个连续的右括号 '))' 。
  • 左括号 '(' 必须在对应的连续两个右括号 '))' 之前。
比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。
你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。
请你返回让 s 平衡的最少插入次数。
现在假设 1 个左括号需要匹配 2 个右括号才叫做有效的括号组合，那么给你输入一个括号串 s，请问你如何计算使得 s 有效的最小插入次数呢？
核心思路还是和刚才一样，通过一个 need 变量记录对右括号的需求数，根据 need 的变化来判断是否需要插入。
仔细分析一下四种情况：
  • 碰到左括号，右括号的需求 +2
    • 如果右括号的需求为奇数，则前面一定少了一个右括号，插入，需求 -1
  • 碰到右括号
    • 如果需求为 0，则前面插入一个左括号，需求 +1（当前有一个了）
    • 如果需求不为 0，则需求 -1