Hot100——栈

有效的括号

给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

示例 5：

输入：s = "([)]"

输出：false

提示：

• 1 <= s.length <= 104
• s仅由括号'()[]{}'组成

class Solution: def isValid(self, s: str) -> bool: if len(s) % 2 == 1: return False pairs = { ")": "(", "]": "[", "}": "{", } stack = list() for ch in s: if ch in pairs: if not stack or stack[-1] != pairs[ch]: return False stack.pop() else: stack.append(ch) return not stack

最小栈

设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。

实现MinStack类:

• MinStack()初始化堆栈对象。
• void push(int val)将元素val推入堆栈。
• void pop()删除堆栈顶部的元素。
• int top()获取堆栈顶部的元素。
• int getMin()获取堆栈中的最小元素。

示例 1:

输入：["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]输出：[null,null,null,null,-3,null,0,-2]解释：MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.

提示：

• -231 <= val <= 231 - 1
• pop、top和getMin操作总是在非空栈上调用
• push,pop,top, andgetMin最多被调用3 * 104次

借用了一个辅助栈min_stack[ ]

class MinStack: def __init__(self): self.stack = [] self.min_stack = [math.inf] def push(self, val: int) -> None: self.stack.append(val) self.min_stack.append(min(val, self.min_stack[-1])) def pop(self) -> None: self.stack.pop() self.min_stack.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.min_stack[-1] # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(val) # obj.pop() # param_3 = obj.top() # param_4 = obj.getMin()

字符串解码