LeetCode Day5 -- 栈、队列、堆
目录
1.栈
1.1 适用场景：需要回退/最近匹配
1.2 普通栈 vs 单调栈
2.队列
2.1 适用场景：需要先进先出/BFS
2.2 普通队列 vs 双端队列
3.堆/优先队列
4.LeetCode
4.1 栈
（1）2390 从字符串中移除星号
（2）735 小行星碰撞
（3）394 字符串解码
4.2 队列
（1）933 最近的请求次数
（2）Dota2参议院
4.3 堆/优先队列
（1）215 数组中的第K个最大元素
（2）2542 最大子序列的分数
（3）373 查找和最小的 K 对数字
1.栈
1.1 适用场景：需要回退/最近匹配
需要处理对称或嵌套结构：括号匹配、表达式求值、XML/JSON解析
需要回溯或撤销操作：浏览器历史、文本编辑器撤销
需要顺序反转或逆序访问：链表反转、行星碰撞
递归或深度优先搜索(DFS)：函数调用栈、图的DFS遍历
保持后进先出顺序处理：单调栈解决"下一个更大元素"问题
1.2 普通栈 vs 单调栈
普通栈更适合需要模拟过程、记录状态的问题
stack = [] # 初始化空栈for element in sequence:# 根据问题决定压栈条件if need_push(element, stack_top):stack.push(element)# 根据问题决定弹栈条件if need_pop(element, stack_top):while stack and condition(element, stack_top):stack.pop()单调栈特别适合解决需要快速找到元素边界关系的问题
（1）决定单调方向：
-- 更大元素问题 → 递减栈
-- 更小元素问题 → 递增栈
（2）存储内容选择：
-- 需要计算距离 → 存储索引
-- 只关心值 → 存储值
（3）哨兵技巧：在数组前后添加极值避免空栈检查
# 以单调递减栈为例
stack = [] # 初始化空栈for i, element in enumerate(sequence):# 核心：维护单调性 - 弹出破坏单调性的元素while stack and element > stack_top: # 对于递减栈，当前元素较大时破坏递减性stack.pop()# 通常在这里计算边界关系（如面积）# 当前元素入栈stack.push(element or i) # 通常存储索引便于计算2.队列
2.1 适用场景：需要先进先出/BFS
需要先进先出(FIFO)处理顺序：缓冲区管理、任务调度
广度优先搜索(BFS)相关：图的最短路径、树的层级遍历
滑动窗口问题：求滑动窗口最大值/最小值
数据流处理：实时处理连续数据
需要控制处理顺序：打印任务排队
2.2 普通队列 vs 双端队列
（1）普通队列 Queue：
遵循先进先出（FIFO）原则。
只允许在队尾添加元素（入队），在队头移除元素（出队）。
主要操作：入队（append）和出队（pop(0)）。
在Python中，使用列表（list）实现普通队列时，
pop(0)操作的时间复杂度为O(n)，因为需要移动所有元素。
（2）双端队列 Deque：
允许在队列的两端（队头和队尾）进行插入和删除操作。
主要操作：在队头添加（appendleft）或删除（popleft），在队尾添加（append）或删除（pop）。
在Python的
collections.deque中，这些操作的时间复杂度都是O(1)，因为它是通过双向链表实现的。
3.堆/优先队列
优先队列是一种抽象数据结构，支持插入元素和提取最高优先级元素，堆是实现优先队列最常用且最高效的数据结构（通常是二叉堆）。→ 堆是优先队列的具体实现方式。
在Python中，heapq 模块提供了堆操作，可用于实现优先队列。
适用场景：需要动态访问最值/部分排序
需要快速访问最值元素：取最大/最小值
部分排序问题：找第K大/小元素
有序合并多个序列：合并K个有序链表/数组
调度/优先级任务：CPU任务调度
贪心算法：Dijkstra最短路径、Huffman编码
4.LeetCode
4.1 栈
（1）2390 从字符串中移除星号
给你一个包含若干星号 * 的字符串 s 。在一步操作中，你可以：
- 选中
s中的一个星号。 - 移除星号 左侧 最近的那个 非星号 字符，并移除该星号自身。
返回移除 所有 星号之后的字符串。
class Solution(object):def removeStars(self, s):""":type s: str:rtype: str"""stack = []for char in s: if char=='*' and stack: # 确保栈非空，避免空栈弹出x = stack.pop()else:stack.append(char)return "".join(stack) # 将字符列表拼接成字符串（2）735 小行星碰撞
给定一个整数数组 asteroids，表示在同一行的小行星。数组中小行星的索引表示它们在空间中的相对位置。对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。找出碰撞后剩下的所有小行星。碰撞规则：两个小行星相互碰撞，较小的小行星会爆炸。如果两颗小行星大小相同，则两颗小行星都会爆炸。两颗移动方向相同的小行星，永远不会发生碰撞。
class Solution(object):def asteroidCollision(self, asteroids):""":type asteroids: List[int]:rtype: List[int]"""stack = []for a in asteroids:# 当前行星向左移动（负）且栈顶行星向右移动（正）才会碰撞while stack and stack[-1] > 0 and a < 0:if stack[-1] < -a: # 栈顶行星较小，移除栈顶行星stack.pop() continue # 继续检查新栈顶elif stack[-1] == -a: # 大小相等，移除栈顶行星stack.pop() # 无论大小相等还是栈顶较大，当前行星都会消失breakelse: # 没有发生碰撞时添加当前行星stack.append(a)return stack（3）394 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
class Solution(object):def decodeString(self, s):""":type s: str:rtype: str"""stack = []curr_string = ""curr_k = 0for char in s: ## char一共4种可能：数字or普通字符or左右括号if char.isdigit(): ## 多位数处理curr_k = curr_k*10 + int(char)elif char=='[': ## 将当前已有内容入栈，开始处理新一轮的字符串stack.append(curr_string)stack.append(curr_k)curr_string = ""curr_k = 0elif char==']': ## 弹出倍数和字符串，按照倍数将当前string与历史string进行拼接k = stack.pop()string = stack.pop()curr_string = string + k*curr_stringelse: ## 处理[]中的内容，将其拼接为完整的stringcurr_string += charreturn curr_string4.2 队列
（1）933 最近的请求次数
请你实现 RecentCounter 类：
RecentCounter()：初始化计数器，请求数为 0 。
int ping(int t)：在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
入队操作：每次调用
ping时，将当前时间戳t加入队列。出队操作：由于时间窗口是固定的（3000 毫秒），我们需要移除所有早于
t-3000的时间戳，因为它们不再属于当前时间窗口。
普通队列：pop(0) 是O(n)操作
class RecentCounter(object):def __init__(self):self.quene = []def ping(self, t):""":type t: int:rtype: int"""self.quene.append(t)while self.quene and self.quene[0]<t-3000:self.quene.pop(0)return len(self.quene) ## 返回发生的请求数# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)双端队列：popleft() 是O(1)操作。对于频繁在队头进行移除操作的场景，使用双端队列是更高效的选择。
import collections
class RecentCounter(object):def __init__(self):self.quene = collections.deque()def ping(self, t):""":type t: int:rtype: int"""self.quene.append(t)while self.quene and self.quene[0]<t-3000:self.quene.popleft()return len(self.quene) ## 返回发生的请求数（2）Dota2参议院
Dota2 的世界里有两个阵营：Radiant（天辉）和 Dire（夜魇）
Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的 一 项：
- 禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失 所有的权利 。
- 宣布胜利：如果参议员发现有权利投票的参议员都是 同一个阵营的 ，他可以宣布胜利并决定在游戏中的有关变化。
给你一个字符串 senate 代表每个参议员的阵营。字母 'R' 和 'D'分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。
以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。
假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 "Radiant" 或 "Dire" 。
1.使用两个队列分别存放两个阵营的参议员序号。
2.比较队头序号值来决定哪个阵营先投票。3.每个参议员会禁止对方下一个将投票的参议员 → pop之后不再放回，永远失去投票权利
4.但该参议员下轮仍可投票，通过添加len来保持原始顺序 → pop后放回，顺延 len 个位置
import collections
class Solution(object):def predictPartyVictory(self, senate):""":type senate: str:rtype: str"""r_quene = collections.deque()d_quene = collections.deque()for i in range(len(senate)):if senate[i]=='R':r_quene.append(i)elif senate[i]=='D':d_quene.append(i)while r_quene and d_quene:r = r_quene.popleft()d = d_quene.popleft()if r<d:# Radiant 参议员投票：禁止 Dire 队列头部成员# 当前参议员保留到下一轮r_quene.append(r+len(senate))elif r>d:# Dire 参议员投票：禁止 Radiant 队列头部成员# 当前参议员保留到下一轮d_quene.append(d+len(senate))if r_quene:return "Radiant"else:return "Dire"4.3 堆/优先队列
（1）215 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
使用堆解决第K大元素的思路
解决"数组中第K个最大元素"问题的最优方法是使用最小堆（Min-Heap）：
1. 维护一个大小为K的最小堆
堆顶元素始终是当前堆中最小的元素 → 这个最小元素就是当前的第K大元素
2. 遍历整个数组
-- 当堆未满（size < K）时，直接将元素加入堆
-- 当堆已满时：如果当前元素大于堆顶，替换堆顶元素；否则忽略当前元素
import heapq
class Solution(object):def findKthLargest(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""min_heap = []for num in nums:if len(min_heap)<k: ## 堆未满时直接加入元素heapq.heappush(min_heap, num)elif min_heap[0]<num: ## 堆满了但当前元素更大，替换堆顶（全堆max）heapq.heapreplace(min_heap, num)return min_heap[0]（2）2542 最大子序列的分数
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都是 n ，再给你一个正整数 k 。你必须从 nums1 中选一个长度为 k 的 子序列 对应的下标。对于选择的下标 i0 ，i1 ，...， ik - 1 ，你的 分数 定义如下：
- nums1 中下标对应元素求和，乘以 nums2 中下标对应元素的 最小值 。
- 用公式表示： (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]) 。
请你返回 最大 可能的分数。
score = 选定的num1之和 * 当前对应的最小num2
① 将两个数组配对pair，按nums2降序排序
② 维护大小为k的（最小）堆，用于存储当前遍历到的最大 num1 值
→ 此时目前输入pair中的num2为当前子序列中的最小值，且num1之和最大
import heapq
class Solution(object):def maxScore(self, nums1, nums2, k):""":type nums1: List[int]:type nums2: List[int]:type k: int:rtype: int"""min_heap = []max_score = 0sum_num1 = 0## 将两个数组的元素配对，并按 nums2 降序排序pairs = sorted(zip(nums1,nums2), key=lambda x:x[1], reverse = True)for num1,num2 in pairs:heapq.heappush(min_heap,num1)sum_num1 += num1if len(min_heap)>k:## 此时子序列变更，加入的nums2只会越来越小，所以需要让nums1保持更大才有可能分数最大## 删除堆中最小元素min_num1 = heapq.heappop(min_heap)sum_num1 -= min_num1if len(min_heap)==k:## 此时nums2为当前子序列中的最小值score = sum_num1*num2max_score = max(score, max_score)return max_score（3）373 查找和最小的 K 对数字
给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk) 。
import heapq
class Solution(object):def kSmallestPairs(self, nums1, nums2, k):""":type nums1: List[int]:type nums2: List[int]:type k: int:rtype: List[List[int]]"""heap=[] ## 堆(sum, num1_index, num2_index)## 每个nums1的前min(k, len)元素与nums2[0]配对入堆for i in range(min(k, len(nums1))): heapq.heappush(heap, (nums1[i]+nums2[0], i, 0)) result=[]while k>0:sum_cur,i,j = heapq.heappop(heap) ## 弹出当前最小数对result.append([nums1[i],nums2[j]]) if j+1<len(nums2): ## 同nums1[i]下，将nums2索引后移一位heapq.heappush(heap, (nums1[i]+nums2[j+1], i, j+1))k-=1return result