Day10，Hot100（栈，堆）

        d = {')':'(', ']':'[', '}':'{'}stack = []for i in s:# 遇到左括号,入栈if i in '([{':stack.append(i)# 遇到右括号,出栈左括号,看是否有匹配的左括号else:if not stack:  # 栈空的时候遇到右括号,则一定不能匹配return Falseif d[i] == stack[-1]:  # 右括号与前面的左括号匹配stack.pop()else:return Falseif not stack:  # 栈为空, 说明全部都匹配成功return Truereturn False

维护一个最小栈，存储当前栈的最小值
栈尾总是当前栈的最小值

• push时需要判断新加入的值是否小于 min_st[-1]
• pop的时候需要判断pop的元素是否是 min_st[-1]

class MinStack:def __init__(self):self.stack = []self.min_st = []  # 保存stack中的最小值def push(self, val: int) -> None:self.stack.append(val)if not self.min_st or self.min_st[-1] >= val:self.min_st.append(val)def pop(self) -> None:if self.stack.pop() == self.min_st[-1]:self.min_st.pop()def top(self) -> int:return self.stack[-1]def getMin(self) -> int:return self.min_st[-1]

示例：3[a2[c]]
递

1. 3[ a2[c] ]
2. a2[c]
3. 2[c]

归

1. 2[c] --> cc
2. a2[c] --> acc
3. 3[ a2[c] ] --> acc acc acc

class Solution:def decodeString(self, s: str) -> str:stack = []res = ''  # 当前解码的字符串multi = 0  # 当前的倍数for c in s:if c == '[':stack.append((res, multi))  # 数字之前的结果,以及数字multi = 0res = ''elif '0' <= c <= '9':multi = multi * 10 + int(c)elif c == ']':last_res, cur_multi = stack.pop()res = last_res + cur_multi * reselse:res += creturn res

单调栈

• 及时去掉无用数据
• 保证栈中元素有序
  

方法一：从左往右遍历：

• 栈内保留还没有找到答案的元素
• 当元素大于栈顶时出栈栈顶， 每次在出栈的时候更新答案，

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n = len(temperatures)ans = [0] * nst = []  # 存储数组下标for i in range(n):t = temperatures[i]while st and t > temperatures[st[-1]]:j = st.pop()ans[j] = i - jst.append(i)return ans

方法二：从右往左遍历：

• 逐步出栈，直到遇到符合条件的温度，更新答案

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n = len(temperatures)ans = [0] * nst = []  # 存储数组下标for i in range(n-1, -1, -1):t = temperatures[i]# 如果栈顶元素小于当天温度,则持续出栈,直到找到while st and t >= temperatures[st[-1]]:st.pop()if st:ans[i] = st[-1] - ist.append(i)return ans                   

最小堆

• 维护一个大小为k的最小堆
• 最终堆顶就是第 k 大的元素

import heapq
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:min_heap = nums[:k]heapq.heapify(min_heap)  # 使用前k个元素构建最小堆# 从第 k+1 个元素开始遍历for num in nums[k:]:if num > min_heap[0]:heapq.heappop(min_heap)  # 弹出堆顶元素heapq.heappush(min_heap, num)  # 插入新的元素return min_heap[0]  # 堆顶元素就是第 K 个最大的元素

最大堆

• 将整个数组堆化，逐个弹出堆顶
• 第 k 个堆顶就是第 k 大的元素

import heapq
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:nums = [-num for num in nums]heapq.heapify(nums)for _ in range(k):res = -heapq.heappop(nums)return res

使用 Counter 统计每个元素的频率
使用最小堆，维护一个大小为 k 的频率

heapq.heappush(heap, (count, num))

• 往heap中加入元素 (count, num)
• 最小堆会自动首先按照第一个元素 count 大小排序，构建最小堆

import heapq
from collections import Counterclass Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:cnt = Counter(nums)  # 统计词频heap = []for num, count in cnt.items():heapq.heappush(heap, (count, num))if len(heap) > k:heapq.heappop(heap)return [num for count, num in heap]