栈

LeetCode 71 https://leetcode.cn/problems/simplify-path/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 使用一个栈存储目录，如果当前字符不是 ‘/’，那么更新 dir，直到遇到 ‘/’。如果 dir 是 “.."，把栈顶目录弹出。如果 dir 不是”."、"..“和空串，添加到栈中。最后使用 ‘/’ 连接目录作为答案。为方便处理，首先在 path 最后添加 ‘/’。 时间复杂度：O(n)，其中 n 是字符串 path 的长度。 空间复杂度：O(n)。我们需要 O(n) 的空间存储 names 中的所有字符串。 ...

LeetCode 678 https://leetcode.cn/problems/valid-parenthesis-string/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 括号匹配的问题可以用栈求解。 如果字符串中没有星号，则只需要一个栈存储左括号，在从左到右遍历字符串的过程中检查括号是否匹配。 在有星号的情况下，需要两个栈分别存储左括号和星号。从左到右遍历字符串，进行如下操作。 如果遇到左括号，则将当前下标存入左括号栈。 如果遇到星号，则将当前下标存入星号栈。 如果遇到右括号，则需要有一个左括号或星号和右括号匹配，由于星号也可以看成右括号或者空字符串，因此当前的右括号应优先和左括号匹配，没有左括号时和星号匹配： 如果左括号栈不为空，则从左括号栈弹出栈顶元素； 如果左括号栈为空且星号栈不为空，则从星号栈弹出栈顶元素； 如果左括号栈和星号栈都为空，则没有字符可以和当前的右括号匹配，返回 false。 遍历结束之后，左括号栈和星号栈可能还有元素。为了将每个左括号匹配，需要将星号看成右括号，且每个左括号必须出现在其匹配的星号之前。当两个栈都不为空时，每次从左括号栈和星号栈分别弹出栈顶元素，对应左括号下标和星号下标，判断是否可以匹配，匹配的条件是左括号下标小于星号下标，如果左括号下标大于星号下标则返回 false。 最终判断左括号栈是否为空。如果左括号栈为空，则左括号全部匹配完毕，剩下的星号都可以看成空字符串，此时 s 是有效的括号字符串，返回 true。如果左括号栈不为空，则还有左括号无法匹配，此时 s 不是有效的括号字符串，返回 false。 时间复杂度：O(n)，其中 n 是字符串 s 的长度。需要遍历字符串一次，遍历过程中每个字符的操作时间都是 O(1)，遍历结束之后对左括号栈和星号栈弹出元素的操作次数不会超过 n。 空间复杂度：O(n)，其中 n 是字符串 s 的长度。空间复杂度主要取决于左括号栈和星号栈，两个栈的元素总数不会超过 n。 ...

LeetCode 225 https://leetcode.cn/problems/implement-stack-using-queues/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 使用一个队列时，为了满足栈的特性，即最后入栈的元素最先出栈，同样需要满足队列前端的元素是最后入栈的元素。 入栈操作时，首先获得入栈前的元素个数 n，然后将元素入队到队列，再将队列中的前 n 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。 由于每次入栈操作都确保队列的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可，获得栈顶元素操作只需要获得队列的前端元素并返回即可（不移除元素）。 由于队列用于存储栈内的元素，判断栈是否为空时，只需要判断队列是否为空即可。 时间复杂度：入栈操作 O(n)，其余操作都是 O(1)，其中 n 是栈内的元素个数。 空间复杂度：O(n)，其中 n 是栈内的元素个数。需要使用一个队列存储栈内的元素。 ...

LCR 125 https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 将一个栈当作输入栈，用于压入 appendTail 传入的数据；另一个栈当作输出栈，用于 deleteHead 操作。 每次 deleteHead 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。 时间复杂度：appendTail 为 O(1)，deleteHead 为均摊 O(1)。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为 O(1)。 空间复杂度：O(n)。其中 n 是操作总数。对于有 n 次 appendTail 操作的情况，队列中会有 n 个元素，故空间复杂度为 O(n)。 ...

LeetCode 224 https://leetcode.cn/problems/basic-calculator/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 由于字符串除了数字与括号外，只有加号和减号两种运算符。因此，如果展开表达式中所有的括号，则得到的新表达式中，数字本身不会发生变化，只是每个数字前面的符号会发生变化。 因此，我们考虑使用一个取值为 {−1,+1} 的整数 sign 代表「当前」的符号。根据括号表达式的性质，它的取值： 与字符串中当前位置的运算符有关； 如果当前位置处于一系列括号之内，则也与这些括号前面的运算符有关：每当遇到一个以 − 号开头的括号，则意味着此后的符号都要被「翻转」。 考虑到第二点，我们需要维护一个栈 ops，其中栈顶元素记录了当前位置所处的每个括号所「共同形成」的符号。例如，对于字符串 1+2+(3-(4+5))： 扫描到 1+2 时，由于当前位置没有被任何括号所包含，则栈顶元素为初始值 +1； 扫描到 1+2+(3 时，当前位置被一个括号所包含，该括号前面的符号为 + 号，因此栈顶元素依然 +1； 扫描到 1+2+(3-(4 时，当前位置被两个括号所包含，分别对应着 + 号和 − 号，由于 + 号和 − 号合并的结果为 − 号，因此栈顶元素变为 −1。 在得到栈 ops 之后， sign 的取值就能够确定了：如果当前遇到了 + 号，则更新 sign = ops.top()；如果遇到了遇到了 − 号，则更新 sign = −ops.top()。 然后，每当遇到 ( 时，都要将当前的 sign 取值压入栈中；每当遇到 ) 时，都从栈中弹出一个元素。这样，我们能够在扫描字符串的时候，即时地更新 ops 中的元素。 时间复杂度：O(n)，其中 n 为字符串 s 的长度。需要遍历字符串 s 一次，计算表达式的值。 空间复杂度：O(n)，其中 n 为字符串 s 的长度。空间复杂度主要取决于栈的空间，栈中的元素数量不超过 n。 ...

LeetCode 283 https://leetcode.cn/problems/move-zeroes/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 题目要求在不复制数组的情况下原地对数组进行操作。 直接把 nums 当作栈，用一个变量 stackSize 表示栈的大小，初始值为 0。 入栈就是把 nums[stackSize] 置为 nums[i]，同时把 stackSize 加一。 最后把 nums 中的下标从 stackSize 到 n−1 的数都置为 0。 时间复杂度：O(n)，其中 n 是 nums 的长度。 空间复杂度：O(1)。 ...

LeetCode 227 https://leetcode.cn/problems/basic-calculator-ii/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是包含加减乘除，但没有括号的表达式求值。可以使用一个栈来解决。 使用 op 记录上一个运算符是什么。遍历字符串，如果当前字符是数字，就更新数字，如果是运算符或者已经到了最后一个字符，那么根据上一个运算符来操作。如果是加减，那么直接将当前数字加入栈中。如果是乘除，直接操作栈顶元素。然后将 op 更新为当前字符。 最后只需要将栈中所有元素加起来即可。为了方便遍历，栈使用 vector 实现。 时间复杂度：O(n)，其中 n 为字符串 s 的长度。需要遍历字符串 s 一次，计算表达式的值。 空间复杂度：O(n)，其中 n 为字符串 s 的长度。空间复杂度主要取决于栈的空间，栈的元素个数不超过 n。 ...

LeetCode 394 https://leetcode.cn/problems/decode-string/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 使用双栈法。一个栈存储数字，一个栈存储字符串。当遇到数字时，更新数字，注意数字可能有多位；遇到字母时，加到当前字符串中；遇到 ‘[’ 时，将将当前字符串和数字入栈；遇到 ‘]’ 时，解码，将数字和字符串出栈，将当前字符串重复 k 次加到栈顶字符串后面，将栈顶字符串更新为当前字符串。 时间复杂度：O(S)。 空间复杂度：O(S)。 ...

LeetCode 155 https://leetcode.cn/problems/min-stack/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 栈存储一个 pair，当前值和前缀最小值，初始化存储一个哨兵节点。 stack<pair<int, int>> st; 时间复杂度：所有操作均为 O(1)。 空间复杂度：O(q)。其中 q 是 push 调用的次数。最坏情况下，只有 push 操作，需要 O(q) 的空间保存元素。 ...

LeetCode 232 https://leetcode.cn/problems/implement-queue-using-stacks/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 用两个栈，输入栈和输出栈来模拟队列。push 时将输入压进输入栈。pop 时，如果输出栈为空，将输出栈的元素全部压入输出栈，这时输出栈的顺序就是输入的顺序。返回输出栈栈顶元素。 时间复杂度：push 和 empty 为 O(1)，pop 和 peek 为均摊 O(1)。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为 O(1)。 空间复杂度：O(n)。其中 n 是操作总数。对于有 n 次 push 操作的情况，队列中会有 n 个元素，故空间复杂度为 O(n)。 ...