栈

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)。 ...

LeetCode 20 https://leetcode.cn/problems/valid-parentheses/description/ 难度：中等 本题是栈的应用。如果是左括号就入栈，如果是右括号，如果栈顶元素与其匹配，则出栈，否则返回 false。最后返回栈是否为空。 时间复杂度：O(n)，其中 n 是 s 的长度。 空间复杂度：O(n)。 ...