栈

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

LeetCode 155 https://leetcode.cn/problems/min-stack/description/ 难度：中等 栈存储一个 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/ 难度：简单 用两个栈，输入栈和输出栈来模拟队列。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)。 ...