5-2 栈和队列相关题目 版权声明：以下题目均来自 LeetCode ， 仅仅提供跳转到力扣官网的链接，不在本页面出现题目内容，本文章内容禁止商业用途。
目录
5.2.1 栈的常见题目：
5.2.1.1 用栈实现队列 LeetCode 232.用栈实现队列 | | 返回目录5.2.1
思路：队列是先入的先出，所以要用一个栈存储数据，另一个栈用来调整顺序。
class MyQueue : def __init__ (self ): self.__s_a = [] self.__s_b = [] def push (self, x: int ) -> None : self.__s_a.append(x) def pop (self ) -> int : while self.__s_a: self.__s_b.append(self.__s_a.pop()) res = self.__s_b.pop() while self.__s_b: self.__s_a.append(self.__s_b.pop()) return res def peek (self ) -> int : while self.__s_a: self.__s_b.append(self.__s_a.pop()) res = self.__s_b[-1 ] while self.__s_b: self.__s_a.append(self.__s_b.pop()) return res def empty (self ) -> bool : return not self.__s_a
5.2.1.2 最小栈 LeetCode 155.最小栈 | | 返回目录5.2.1
思路1：用一个栈维护数据，再用另一个栈维护最小值。数据栈在进行入栈、出栈操作时，也要同时对最小值栈进行操作。
class MinStack : import math def __init__ (self ): self.__stack_list=[] self.__min_list=[] def push (self, val: int ) -> None : self.__stack_list.append(val) if self.__min_list: min_v = min (val, self.__min_list[-1 ]) self.__min_list.append(min_v) else : self.__min_list.append(val) def pop (self ) -> None : if self.__stack_list: self.__stack_list.pop() self.__min_list.pop() return def top (self ) -> int : if self.__stack_list: return self.__stack_list[-1 ] else : return math.nan def getMin (self ) -> int : if self.__min_list: return self.__min_list[-1 ] else : return math.nan
思路2：由于思路1中用到了一个辅助栈，空间的消耗会是原始数据的2倍。这里可以考虑一个不用辅助栈的方案.
class MinStack : def __init__ (self ): self.__delta_stack = [] self.__minv = -1 def push (self, val: int ) -> None : if len (self.__delta_stack) == 0 : self.__minv = val self.__delta_stack.append(0 ) else : delta = val - self.__minv if delta < 0 : self.__minv = val self.__delta_stack.append(delta) def pop (self ) -> None : if self.__delta_stack: delta = self.__delta_stack.pop() if delta < 0 : val = self.__minv self.__minv = val - delta else : val = delta + self.__minv return val else : return None def top (self ) -> int : if self.__delta_stack: delta = self.__delta_stack[-1 ] return self.__minv if delta < 0 else delta+self.__minv else : return None def getMin (self ) -> int : return self.__minv if self.__delta_stack else None
5.2.1.3 删除字符串中的所有相邻重复项 LeetCode 1047.删除字符串中的所有相邻重复项 | | 返回目录5.2.1
方案：用一个栈来循环装入每个字符，每个字符入栈时，都要与栈顶元素（即前一个字符）对比一下，若不相同才装入；若相同就不装入，同时删除栈顶元素。
class Solution : def removeDuplicates (self, s: str ) -> str : char_s = [] for ch in s: if char_s: if ch == char_s[-1 ]: char_s.pop() continue char_s.append(ch) return '' .join(char_s)
5.2.1.4 有效的括号 LeetCode 20.有效的括号 | | 返回目录5.2.1
方案：和上面的 5.2.1.2 的思想类似，只不过上面是成对的消字符，这里是成对的消除括号，原理是一样的。如果中途就碰见不能消除的情况，就返回False了。最终消除完之后看看是否还剩的有括号
class Solution : def isValid (self, s: str ) -> bool : bracket_s = [] for ch in s: if ch == '(' or ch == '[' or ch == '{' : bracket_s.append(ch) elif ch == ')' : if bracket_s and bracket_s[-1 ] == '(' : bracket_s.pop() else : return False elif ch == ']' : if bracket_s and bracket_s[-1 ] == '[' : bracket_s.pop() else : return False elif ch == '}' : if bracket_s and bracket_s[-1 ] == '{' : bracket_s.pop() else : return False return len (bracket_s) == 0
5.2.1.5 最长有效括号 LeetCode 32.最长有效括号 | |返回目录5.2.1
方案：此题依旧和上面两个题是一样的原理，做消消乐。同样是成对的消括号，只不过这一次要算一下消除的区域的长度。一个很自然的想法就是：需要消掉的部分的最后一个字符的索引index，减去尚未被消除的部分的最后一个字符的索引index，就是此次消除区域的长度gap。最后要得到的是最长的这个gap，只需要每次用一个max函数更新一下就行。
'''code version.1''' class Solution : def longestValidParentheses (self, s: str ) -> int : stack, gap = [[')' , -1 ]], 0 for i in range (len (s)): ch = s[i] if ch == '(' : stack.append([ch, i]) else : if stack[-1 ][0 ] =='(' : stack.pop() gap = max (gap, i-stack[-1 ][1 ]) else : stack[-1 ][1 ] = i return gap
''' code version.2 上面的code中，栈每次入栈的时候，同时存下了(符号，索引)， 两个数据； 这样的好处是便于理解，从直观上看和我们上面的题目的code能统一； 但是辅助栈消耗的空间就较大了，这里可以在原有的基础上进一步update ''' class Solution : def longestValidParentheses (self, s: str ) -> int : stack, gap = [-1 ], 0 for i in range (len (s)): ch = s[i] if ch == '(' : stack.append(i) else : stack.pop() if stack: gap = max (gap, i-stack[-1 ]) else : stack.append(i) return gap
5.2.1.6 基本计算器 LeetCode 224.基本计算器 | | 返回目录5.2.1
方案：
另一种思路，那就是消掉括号，把式子改写为没有括号的情况，而且由于只涉及到加、减运算，消掉括号后依然能保持从左往右的基本计算顺序，只要保证消括号时数字前面的运算符能够完成转换即可。
这里采用第二种思路，消括号的思路。 如果把一对括号( )包含的区域视为一个整体的话，这个整体都会受到括号外的正/负号的影响。
此外该题目还隐藏了一个陷阱： 题目举的例子中都是个位数 。如果遇到十位、百位不为空的情况，是需要注意，这个数字也会按照字符被分割开。比如12会被分割成1和2的字符依次输入，我们需要将其还原为原始的12！
class Solution : def calculate (self, s: str ) -> int : num, preSign = 0 , 1 sign_list = [1 ] res = 0 for ch in s + '+' : if ch == ' ' : continue elif ch.isdigit(): num = num*10 + ord (ch) - ord ('0' ) else : res += preSign * num num = 0 if ch in '-+' : preSign = sign_list[-1 ]*(-1 if ch == '-' else 1 ) elif ch == '(' : sign_list.append(preSign) elif ch == ')' : sign_list.pop() return res
5.2.1.7 基本计算器Ⅱ LeetCode 227.基本计算器II | | 返回目录5.2.1
方案：
class Solution : def calculate (self, s: str ) -> int : num_stack = [] preSign = '+' num = 0 for ch in s+'+' : if ch == ' ' : continue elif ch.isdigit(): num = num*10 + ord (ch) - ord ('0' ) else : if preSign == '+' : num_stack.append(num) elif preSign == '-' : num_stack.append(-num) elif preSign == '*' : num_stack.append(num_stack.pop() * num) else : num_stack.append(int (num_stack.pop() / num)) num = 0 preSign = ch return sum (num_stack)
5.2.1.8 字符串解码 LeetCode 394.字符串解码 | | 返回目录5.2.1
这个题的思想和 5.2.1.6 很相似，也是有括号，只不过这里是中括号[ ];
class Solution : def decodeString (self, s: str ) -> str : num, tmp_str = 0 , '' num_list, str_list = [], [] for ch in s: if ch.isdigit(): num = num*10 + ord (ch) - ord ('0' ) elif ch.isalpha(): tmp_str += ch elif ch == '[' : num_list.append(num) num = 0 str_list.append(tmp_str) tmp_str = '' else : out_num = num_list.pop() out_str = str_list.pop() tmp_str = out_str + out_num * tmp_str return tmp_str
5.2.1.9 逆波兰表达式求值 LeetCode 150.逆波兰表达式求值 | | 返回目录5.2.1
方案：该题的思路其实在例3中已经体现出来了，就是观察规律而已。
class Solution : def evalRPN (self, tokens: List [str ] ) -> int : s = [] for ch in tokens: if ch not in "+-*/" : s.append(int (ch)) else : a2 = s.pop() a1 = s.pop() if ch == '+' : s.append(a1+a2) elif ch == '-' : s.append(a1-a2) elif ch == '*' : s.append(a1*a2) else : s.append(int (a1/a2)) return s[0 ]
5.2.1.10 验证栈序列 LeetCode 946. 验证栈序列 | | 返回目录5.2.1
方案：此题主要是模拟栈的压入压出操作。
class Solution : def validateStackSequences (self, pushed: List [int ], popped: List [int ] ) -> bool : s, i = [], 0 for num in pushed: s.append(num) while (s and s[-1 ] == popped[i]): s.pop() i+=1 return len (s) == 0
5.2.2 单调栈 所谓单调栈，就是从栈顶到栈底的方向上是单调递增(减)，所以其实从栈底到栈顶的方向也是单调的。（因为python中一般用 list 来当栈用，所以从序号0开始看的话，我们一般都是看栈底到栈顶的方向。）
单调栈如何用操作呢？假设讨论单调递增的情况，如果一个元素比栈顶的元素大，我们才入栈；否则就先pop掉栈顶元素，然后继续比；直到满足等待入栈的元素比栈顶元素大了，或者栈已经为空了，才入栈。这样栈中的元素就是能保持单调递增的关系 。
5.2.2.0 解法总结 单调栈通常被用来解决：求上一个更大（小）值 和 下一个更大（小）值的问题，如果遇到这类题型，其核心code的写法几乎都是差不多的，在这里先总结一下。
''' 假设 数据列表是 data_lt, 单调栈是 help_s ； 在下面讨论的情况中，单调栈存储的都是索引值index''' '''(1) 求下一个更大值 ''' while help_s and data_lt[help_s[-1 ]] < data_lt[i]: old_i = help_s.pop() gap[old_i] = i - old_i next_big_id[old_i] = i help_s.append(i) '''(4) 求下一个更小值''' while help_s and data_lt[help_s[-1 ]] > data_lt[i]: old_i = help_s.pop() gap[old_i] = i - old_i next_small_id[old_i] = i help_s.append(i) '''(3) 求上一个更大值 ''' while help_s and data_lt[help_s[-1 ]] <= data_lt[i]: help_s.pop() last_big_id[i] = help_s[-1 ] if help_s else -1 gap[i] = i - help_s[-1 ] if help_s else i help_s.append(i) '''(4) 上一个更小值 ''' while help_s and data_lt[help_s[-1 ]] >= data_lt[i]: help_s.pop() last_small_id = help_s[-1 ] if help_s else -1 gap[i] = i - help_s[-1 ] if help_s else i help_s.append(i) ''' 找更大 、 更小时，栈里的数据 '''
5.2.2.1 每日温度 LeetCode 739.每日温度 | | 返回目录5.2.2
方案：
class Solution : def dailyTemperatures (self, temperatures: List [int ] ) -> List [int ]: s = [] N = len (temperatures) gap = [0 ]*N for i in range (N): while s and temperatures[i] > temperatures[s[-1 ]]: lower_i = s.pop() gap[lower_i] = i - lower_i s.append(i) return gap
5.2.2.2 下一个更大元素I LeetCode 496.下一个更大元素 I | | 返回目录5.2.2
方案:问题分为两个子问题:
'''方案1. 暴力求解''' class Solution : def nextGreaterElement (self, nums1: List [int ], nums2: List [int ] ) -> List [int ]: hash_l = {} N2 = len (nums2) for i, num in enumerate (nums2): hash_l[num] = i res = [] for num in nums1: index = hash_l[num] flag = False while index < N2 and not flag: if nums2[index] > num: res.append(nums2[index]) flag = True index += 1 if not flag: res.append(-1 ) return res
'''方案2. 利用单调栈，借鉴【5.2.8 每日温度】的解法''' class Solution : def nextGreaterElement (self, nums1: List [int ], nums2: List [int ] ) -> List [int ]: h={} N = len (nums2) s, next_big_val = [], [-1 ]*N for i in range (N): h[nums2[i]]=i while s and nums2[s[-1 ]] < nums2[i]: lower_i = s.pop() next_big_val[lower_i] = nums2[i] s.append(i) return [next_big_val[h[num]] for num in nums1]
5.2.2.3 下一个更大元素 II LeetCode 503.下一个更大元素 II | | 返回目录5.2.2
方案：问题本质依旧是【求下一个更大数】；核心点在于数组可以循环。
'''1.最简单的思路，就是把原来数组扩充一倍， 只不过返回结果的时候，只返回前N个就可以了''' class Solution : def nextGreaterElements (self, nums: List [int ] ) -> List [int ]: N = len (nums) s, res = [], [-1 ]*2 *N nums2 = nums + nums for i in range (len (nums2)): while s and nums2[i] > nums2[s[-1 ]]: tmp_i = s.pop() res[tmp_i] = nums2[i] s.append(i) return res[0 :N]
'''方案1稍微有点耗内存，可以考虑不用扩充数组的方式来循环，即求模运算。 但求模可能又会多花点时间''' class Solution : def nextGreaterElements (self, nums: List [int ] ) -> List [int ]: s = [] N = len (nums) next_big_val = [-1 ]*N for i in range (2 *N): while s and nums[s[-1 ]] < nums[i%N]: lower_i = s.pop() next_big_val[lower_i] = nums[i%N] s.append(i%N) return next_big_val
5.2.2.4 股票价格跨度 LeetCode 901.股票价格跨度 | | 返回目录5.2.2
方案：问题本质：【求上一个更大数】。gap是当前 i 位置与上一个更大元素的位置的gap。那么在这个gap区间，所有的数都是小于当前值的，这就是该题要求的跨度。
class StockSpanner : def __init__ (self ): self.__s = [] self.__data = [] self.__len = 0 def next (self, price: int ) -> int : self.__len +=1 self.__data.append(price) i = self.__len - 1 while self.__s and self.__data[self.__s[-1 ]] <= price: self.__s.pop() gap = i- self.__s[-1 ] if self.__s else self.__len self.__s.append(i) return gap
5.2.2.5 柱状图中最大的矩形 LeetCode 84.柱状图中最大的矩形 | | 返回目录5.2.2
方案：问题就转化成了：【上一个更小数】，和【下一个更小数】
class Solution : def largestRectangleArea (self, heights: List [int ] ) -> int : N = len (heights) left_small_list, right_small_list = [-1 ]*N, [N]*N L_s, R_S = [], [] res = [] for i in range (N): while L_s and heights[i] <= heights[L_s[-1 ]]: L_s.pop() left_small_list[i] = L_s[-1 ] if L_s else -1 L_s.append(i) while R_S and heights[i] < heights[R_S[-1 ]]: larger_i = R_S.pop() right_small_list[larger_i] = i R_S.append(i) return max ([heights[i]*(right_small_list[i] - left_small_list[i]-1 ) for i in range (N)])
5.2.2.7 接雨水 LeetCode 42.接雨水 | | 返回目录5.2.2
该题在处已经讲过，但是同样可以用单调栈来做。
''' 单调栈解法''' class Solution : def trap (self, height: List [int ] ) -> int : N = len (height) water = 0 if N <3 : return water s = [] for i in range (N): while s and height[i] > height[s[-1 ]]: tmp = s.pop() if s: L = s[-1 ] W = i - L -1 H = min (height[L], height[i]) - height[tmp] water += W * H s.append(i) return water
5.2.3 队列的常见题目：
5.2.3.1 用队列实现栈 LeetCode 225.用队列实现栈 | | 返回目录5.2.3
方案：核心点在于队列只能从队首元素出队，也就是说，先进的先出；而栈是后进的先出。
class MyStack : def __init__ (self ): from collections import deque self.__q_a = deque([]) self.__q_b = deque([]) def push (self, x: int ) -> None : if not self.__q_a and not self.__q_b: self.__q_a.append(x) elif not self.__q_a: self.__q_b.append(x) else : self.__q_a.append(x) def pop (self ) -> int : if self.__q_a: while len (self.__q_a)>1 : self.__q_b.append(self.__q_a.popleft()) return self.__q_a.popleft() elif self.__q_b: while len (self.__q_b)> 1 : self.__q_a.append(self.__q_b.popleft()) return self.__q_b.popleft() else : return None def top (self ) -> int : if self.__q_a: return self.__q_a[-1 ] else : return self.__q_b[-1 ] def empty (self ) -> bool : if not self.__q_a and not self.__q_b: return True else : return False
5.2.3.2 设计循环队列 LeetCode 622.设计循环队列 | | 返回目录5.2.3
思路：
class MyCircularQueue : def __init__ (self, k: int ): self.__cycle_q = [-999 ] *(k+1 ) self.__head = 0 self.__tail = 0 self.__len = k+1 def enQueue (self, value: int ) -> bool : if self.isFull(): return False else : self.__cycle_q[self.__tail] = value self.__tail = (self.__tail+1 ) % self.__len return True def deQueue (self ) -> bool : if self.isEmpty(): return False else : self.__head = (self.__head+1 ) % self.__len return True def Front (self ) -> int : if self.isEmpty(): return -1 else : return self.__cycle_q[self.__head] def Rear (self ) -> int : if self.isEmpty(): return -1 else : return self.__cycle_q[self.__tail-1 ] def isEmpty (self ) -> bool : return self.__head == self.__tail def isFull (self ) -> bool : return (self.__tail+1 ) % self.__len == self.__head
5.2.4 优先队列： 优先队列，是一种特殊的队列。它的增加和删除元素的方式和普通队列一样，入队从队尾增加元素，出队删除队头元素。区别点在于，普通队列的内部元素顺序就是按照元素入队列的顺序排布的，而优先队列自己会将内部元素按照一定的顺序进行排布。
也就是说，在新元素添加到队尾之后，队列会自己将这个新元素放到合适的位置，使得满足其顺序定义。而在出队列操作，弹出队首元素后，队列也会对剩下的元素重新梳理一遍顺序。而这个顺序，其实就是之前在排序章节，堆排序部分，讲过的堆结构的顺序。
所以优先队列也被称为堆队列(Heap queue)，可以理解为大（小）根堆。python中有自带的优先队列的库:heapq， 官方文档点击此处 。官方源码点击此处 。
import heapqlist_test = [10 ,7 ,8 ,9 ,5 ,6 ,4 ,2 ,1 ,0 ] ''' 1.heapify 将list转换为一个 小根堆，最小的元素会被放到队首（根节点） ''' heapq.heapify(list_test) print (list_test)''' 2.heappush 将新元素插入末尾，并按照小根堆的顺序排序 ''' heapq.heappush(list_test, -1 ) heapq.heappush(list_test, 20 ) print (list_test)''' 3.heappop 将队首元素（根节点）弹出，并将剩下的元素恢复成小根堆 ''' top = heapq.heappop(list_test) print (list_test)print (top)''' 4.heapreplace 同时执行heappop和heappush，但注意，操作顺序是： 先pop队首元素，然后push新元素 ''' top2 = heapq.heapreplace(list_test, 11 ) print (list_test)print (top2)''' 5.heappushpop 同时执行heappush和heappop， 这里先push新元素，然后再pop队首元素 ''' top3 = heapq.heappushpop(list_test, -10 ) print (list_test)print (top3)''' 6.merge # 将多个堆合并,合并后的结果也是小根堆 ''' a = [10 , 7 , 6 ] b = [1 , 4 , 5 ] c = heapq.merge(a,b) print (c, list (c))''' 7.nlargest 查询堆中的最大n个元素， 并返回 ''' nlarge = heapq.nlargest(3 , list_test) print (nlarge)''' 8.nsmallest # 查询堆中的最小n个元素 ''' nsmall = heapq.nsmallest(3 , list_test) print (nsmall)print ("*" *10 )''' 9._heapify_max # 构造大根堆 # 注意, 对于数值型数据，一般都不会用到建立大根堆的操作 # 因为将数值取反，建立小根堆，就能完成大根堆的目的 # 举例： list_new = list(map(lambda x : -x, list_test)) ''' heapq._heapify_max(list_test) print (list_test)
5.2.4.1 滑动窗口最大值 LeetCode 239.滑动窗口最大值 | | 返回目录5.2.4
思路：滑动窗口是典型的用优先队列的题目。如果直接使用暴力方法，一般都会超时。heapq默认建立的是小根堆，我们只需要把元素取反即可适应它的默认结构，获取结果时记得取反取回来就好
class Solution : def maxSlidingWindow (self, nums: List [int ], k: int ) -> List [int ]: N = len (nums) if N <= k: return [max (nums)] import heapq window = [(-nums[i], i) for i in range (k)] heapq.heapify(window) res = [-window[0 ][0 ]] for i in range (k, N): while window and window[0 ][1 ] < i-k+1 : heapq.heappop(window) heapq.heappush(window, (-nums[i], i)) res.append(-window[0 ][0 ]) '''值得注意的是，堆的规模其实并不一定会维持在k的大小； 因为pop操作只是在堆顶元素不在窗口内时执行； 有一些元素如果已经不在窗口内，但是其并不在堆顶的话，并不影响我们取值； 所以可以留在堆里不用管； 核心是，要保证每一次的堆顶元素，要在考察的窗口内！''' return res
5.2.4.2 数据流中的第 K 大元素 LeetCode 703.数据流中的第 K 大元素 | | 返回目录5.2.4
思路：因为要返回第K大的元素，所以每新到一个数，我们就需要将其与原来的前k大的元素相比较，然后判断这个新的数是否能够被划入前 k 大的元素中，并可以丢弃那些已经不在前k大范围内的数。
import heapqclass KthLargest : def __init__ (self, k: int , nums: List [int ] ): self.__nums = nums heapq.heapify(self.__nums) self.__k = k def add (self, val: int ) -> int : heapq.heappush(self.__nums, val) while len (self.__nums) > self.__k: heapq.heappop(self.__nums) return self.__nums[0 ]
5.2.4.3 数组中的第K个最大元素 LeetCode 215.数组中的第K个最大元素 | | 返回目录5.2.4
思路：该题之前在3-3 排序相关题目 的 3.3.10 已经做过，当时是采用的排序算法，堆方案中也是手写的函数；这里尝试直接使用python自带的优先队列来写code。
写法一：对数组整体应用优先队列，然后再执行k-1次pop操作
import heapqclass Solution : def findKthLargest (self, nums: List [int ], k: int ) -> int : '''写法1：使用默认的小根堆函数，所以需要先手动将数组取反''' nums_new = list (map (lambda x:-x,nums)) heapq.heapify(nums_new) for _ in range (k-1 ): heapq.heappop(nums_new) return -nums_new[0 ] '''2.如果对函数熟悉的话，直接使用大根堆的函数'''
写法二：像5.2.2.2 那样，维护一个k大小的小根堆
import heapqclass Solution : def findKthLargest (self, nums: List [int ], k: int ) -> int : tmp = nums[:k].copy() heapq.heapify(tmp) for i in range (k,len (nums)): heapq.heappushpop(tmp, (nums[i])) return tmp[0 ]
5.2.4.4 前 K 个高频元素 LeetCode 347.前 K 个高频元素 | | 返回目录5.2.4
class Solution : def topKFrequent (self, nums: List [int ], k: int ) -> List [int ]: import heapq h = {} for num in nums: if num not in h: h[num] = 1 else : h[num] += 1 N = len (h) new_nums = [(freq, num) for num, freq in h.items() ] q = new_nums[:k] heapq.heapify(q) for i in range (k,N): heapq.heappushpop(q, new_nums[i]) return [data[1 ] for data in q]
5.2.4.5 根据字符出现频率排序 LeetCode 451.根据字符出现频率排序 | | 返回目录5.2.4
思路：这个题和上题很相似，也是先统计频率，然后可以依据频率排序，也可以用优先队列做，两种写法都给出在下面。
class Solution : def frequencySort (self, s: str ) -> str : h = {} for ch in s: if ch not in h: h[ch] = 1 else : h[ch] += 1 '''1.排序后再处理''' '''2.使用优先队列''' s2 = '' import heapq tmp = [(v,k) for k,v in h.items()] heapq.heapify(tmp) while len (tmp)> 0 : freq, ch = heapq.heappop(tmp) s2 = ch*freq + s2 return s2
5.2.4.6 数据流的中位数 LeetCode 295.数据流的中位数 | | 返回目录5.2.4
思路：题目首先给了中位数的定义，是要在有序数组中进行查找。但是并没有保证输入的数据，一定是有序的。
这里就可以分为两个堆，一个大根堆，存储小于等于中位数的那一半数字，这样它的堆顶(根节点)就是这一半数字中最接近中位数的那个；一个小根堆，存储大于等于中位数的那一半数字，这样它的堆顶(根节点)，也是最接近中位数的那个数。为了方便起见，始终保持前半部分的数目 大于等于后半部分，
import heapqclass MedianFinder : def __init__ (self ): self._left_heap = [] self._right_heap = [] self.__length = 0 def addNum (self, num: int ) -> None : self.__length += 1 if len (self._left_heap) == 0 or num <= -self._left_heap[0 ]: heapq.heappush(self._left_heap, -num) if len (self._left_heap) > len (self._right_heap) + 1 : heapq.heappush(self._right_heap, -heapq.heappop(self._left_heap)) else : heapq.heappush(self._right_heap, num) if len (self._right_heap) > len (self._left_heap): heapq.heappush(self._left_heap, -heapq.heappop(self._right_heap)) def findMedian (self ) -> float : if len (self._left_heap) > len (self._right_heap): return -self._left_heap[0 ] else : return (-self._left_heap[0 ] + self._right_heap[0 ]) / 2 def print (self ): print ("self._left_heap: " , self._left_heap) print ("self._right_heap: " , self._right_heap)
5.2.4.7 最接近原点的 K 个点 LeetCode 973.最接近原点的 K 个点 | | 返回目录5.2.4
思路：这个题最在排序部分也总结过，当时用的是排序的方法。
import heapqclass Solution : def kClosest (self, points: List [List [int ]], k: int ) -> List [List [int ]]: q = [(-x ** 2 - y ** 2 , i) for i, (x, y) in enumerate (points[:k])] heapq.heapify(q) N = len (points) for i in range (k, N): x, y = points[i] d = -(x ** 2 + y ** 2 ) heapq.heappushpop(q, (d, i)) res = [points[idx] for (_, idx) in q] return res
