栈（Stack）的逻辑核心是后进先出（LIFO, Last In First Out）。在处理具有'嵌套'、'匹配'或'寻找最近一个更大/更小'这类问题时，栈是非常强大的工具。
1. 有效的括号 (LeetCode 20)
核心思想：匹配消消乐。
- 直观思路：
- 遍历字符串，遇到左括号
([{就入栈。 - 遇到右括号
)]}，就看栈顶是不是对应的左括号。 - 如果是，就'抵消'（出栈）；如果不是或者栈空了，说明非法。
- 最后如果栈空了，说明全部匹配成功。
- 遍历字符串，遇到左括号
- 复杂度： 时间 O(N)，空间 O(N)。
代码实现 (Python):
def isValid(s: str) -> bool:
stack = []
mapping = {")": "(", "]": "[", "}": "{"}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack
2. 最小栈 (LeetCode 155)
核心思想：同步辅助栈。
- 直观思路：
- 普通的栈无法在 O(1) 时间内找到最小值，因为最小值可能被压在下面。
- 解决： 准备一个辅助栈
min_stack，它和主栈同步。 - 辅助栈的每个位置存：'主栈从底部到当前位置为止的最小值'。
- 这样，无论主栈怎么弹出，辅助栈的顶部永远是当前剩下的数里的最小值。
- 复杂度： O(1) 时间完成所有操作。
代码实现 (Python):
class :
():
.stack = []
.min_stack = []
() -> :
.stack.append(val)
.min_stack val < .min_stack[-]:
.min_stack.append(val)
:
.min_stack.append(.min_stack[-])
() -> :
.stack.pop()
.min_stack.pop()
() -> :
.stack[-]
() -> :
.min_stack[-]
