前言
Python自带的库包含了挺多常用的数据结构，巧妙地利用这些自带的数据结构，能够大大提高解题/实现的效率。下面介绍两种常用的数据结构：
- 优先队列
- 最大（小）堆
数据结构介绍
优先队列
简单介绍
所谓优先队列，其含义是队列中的每个元素都有各自的优先级。其中得到最高优先级的元素，其时间复杂度为O（1）。
应用场景
常用于求区域内最大最小值的问题；采用优先队列通常可以得到O（n）的解法，带有一定的技巧性
简单实现
可以基于
collections.deque双向队列来简单实现，双向队列想较于list的优势在于：其基于双向链表实现，其左右侧插入删除的时间复杂度都为O(1)。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
from collections import deque nums = deque(sorted([1, 45, 2, 4, 61, 5])) # 随机输入的数组,得到排序后的结果 print(nums) # deque([1, 2, 4, 5, 45, 61]) # 后侧新插入元素，需要继续保持优先队列特性，且对前面的元素进行压缩 inserted_num = 20 while (inserted_num < nums[-1]): nums.pop() nums.append(inserted_num) print(nums) # deque([1, 2, 4, 5, 20]) # 前侧新插入元素，需要继续保持优先队列特性，且对后面的元素进行压缩 inserted_num = 3 while (inserted_num > nums[-1]): nums.popleft() nums.appendleft(inserted_num) print(nums) # deque([3, 4, 5, 20])
最大（小）堆
简单介绍
最大（小）堆是常用的数据结构，其通过构造完全二叉树实现；其中构建堆的时间复杂度为O（nlogn），堆元素的插入以及删除调整操作时间复杂度为log（n）。堆排序属于比较稳定的排序。
应用场景
最大（小）堆的优势是能够快速获取最大/最小元素，其时间复杂度为O（1），能够解决大部分topk以及需要动态维护的数据结构的问题。
简单实现
heapq模块实现了最小堆，下面简单介绍其基本操作：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
import heapq l = [1, 23, 4, 5 , 54, 45] # 随机构建的输入 # 原地修改 heapq.heapify(l) print(l) # [1, 5, 4, 23, 54, 45] # 获取最小数并弹出: 堆顶，会自动调整堆结构 print(heapq.heappop(l)) # 1 print(l) # [4, 5, 45, 23, 54] # 插入元素 inserted_num = 0 heapq.heappush(l, inserted_num) print(l) # [0, 5, 4, 23, 54, 45]
实战解析
贴一道Leetcode Hard的真题，分别采用：基本解法/最大堆/优先队列三种解法，可以感受下区别：
题目：239. 滑动窗口最大值
解法如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
from collections import deque
import heapq
class Solution:
@staticmethod
def getmaxvalue(nums):
max_value = float('-inf')
for num in nums:
if num > max_value:
max_value = num
return max_value
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
# 最基础：O(nk)
# 进阶：O(nlog(k))，最大堆
# 最终：O(n)，单调栈
if len(nums) <= k:
return [Solution.getmaxvalue(nums)]
# 基础版本,通过率：49/61
window = deque()
res = []
for num in nums:
window.append(num)
if len(window) >= k:
res.append(Solution.getmaxvalue(window))
window.popleft()
# 进阶版本, 最大堆，all pass
windows = [(-nums[idx], idx) for idx in range(k)]
heapq.heapify(windows)
res = [-windows[0][0]]
for idx, num in enumerate(nums[k:]):
heapq.heappush(windows, (-num, idx + k))
while (windows[0][1] <= idx):
heapq.heappop(windows)
res.append(-windows[0][0])
# 最终版本，单调队列（递增）
windows = deque()
for idx in range(k):
while windows and nums[windows[-1]] <= nums[idx]:
windows.pop()
windows.append(idx)
res = [nums[windows[0]]]
for idx, num in enumerate(nums[k:]):
while windows and nums[windows[-1]] <= num:
windows.pop()
windows.append(idx + k)
while(windows[0] <= idx):
windows.popleft()
res.append(nums[windows[0]])
return res