二分查找
搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
输入: nums = [1,3,5,6], target = 5
输出: 2
nums 为 无重复元素 的 升序 排列数组
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
58
59
60
|
from typing import List
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
"""
使用二分查找找到目标值或插入位置
思路：
- 标准的二分查找模板
- 当 left <= right 时继续循环
- 如果 nums[mid] == target，返回 mid
- 如果 nums[mid] < target，left = mid + 1
- 如果 nums[mid] > target，right = mid - 1
- 循环结束后，left 就是插入位置
- 时间 O(log n)，空间 O(1)
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
# left 就是插入位置
return left
# 测试用例
assert Solution().searchInsert([1, 3, 5, 6], 5) == 2
assert Solution().searchInsert([1, 3, 5, 6], 2) == 1
assert Solution().searchInsert([1, 3, 5, 6], 7) == 4
assert Solution().searchInsert([1, 3, 5, 6], 0) == 0
assert Solution().searchInsert([1], 1) == 0
assert Solution().searchInsert([], 1) == 0
# 手动推导 nums=[1,3,5,6], target=2：
# left=0, right=3, mid=1
# nums[1]=3 > 2, right=0
# left=0, right=0, mid=0
# nums[0]=1 < 2, left=1
# left=1 > right=0，退出
# 返回 left=1
# 结果：1
# 手动推导 nums=[1,3,5,6], target=7：
# left=0, right=3, mid=1
# nums[1]=3 < 7, left=2
# left=2, right=3, mid=2
# nums[2]=5 < 7, left=3
# left=3, right=3, mid=3
# nums[3]=6 < 7, left=4
# left=4 > right=3，退出
# 返回 left=4
# 结果：4
|
搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
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
58
59
60
61
62
63
|
from typing import List
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
"""
将二维矩阵看作一维有序数组进行二分查找
思路：
- 由于每行的第一个整数大于前一行的最后一个整数
- 可以将整个矩阵看作一个升序的一维数组
- 索引 idx 在矩阵中的位置：
- 行号 row = idx // n
- 列号 col = idx % n
- 标准的二分查找
- 时间 O(log(m*n)) = O(log m + log n)，空间 O(1)
也可以用两次二分：先二分找到所在行，再二分在行内查找
"""
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
mid = (left + right) // 2
row = mid // n
col = mid % n
mid_val = matrix[row][col]
if mid_val == target:
return True
elif mid_val < target:
left = mid + 1
else:
right = mid - 1
return False
# 测试用例
assert Solution().searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 3) == True
assert Solution().searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 13) == False
assert Solution().searchMatrix([[1]], 1) == True
assert Solution().searchMatrix([[1]], 2) == False
assert Solution().searchMatrix([[1, 3]], 3) == True
# 手动推导 matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]], target=3：
# m=3, n=4, 总长度=12
# left=0, right=11, mid=5
# row=5//4=1, col=5%4=1, mid_val=matrix[1][1]=11
# 11 > 3, right=4
# left=0, right=4, mid=2
# row=2//4=0, col=2%4=2, mid_val=matrix[0][2]=5
# 5 > 3, right=1
# left=0, right=1, mid=0
# row=0, col=0, mid_val=matrix[0][0]=1
# 1 < 3, left=1
# left=1, right=1, mid=1
# row=1, col=1, mid_val=matrix[0][1]=3
# 3 == 3, 找到！返回 True
# 结果：True
|
在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
nums 是一个非递减数组
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
58
59
60
61
62
63
64
65
66
67
68
|
from typing import List
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
"""
使用二分查找分别找左边界和右边界
思路：
- 核心：二分查找时，当找到 target 时不立即返回，而是继续缩小范围
- 找左边界：当 nums[mid] == target 时，right = mid - 1
- 找右边界：当 nums[mid] == target 时，left = mid + 1
- 最后 left 指向右边界+1，right 指向左边界-1
- 时间 O(log n)，空间 O(1)
"""
if not nums:
return [-1, -1]
# 找左边界
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
left_bound = left
# 找右边界
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] > target:
right = mid - 1
else:
left = mid + 1
right_bound = right
# 检查是否找到
if left_bound < len(nums) and nums[left_bound] == target:
return [left_bound, right_bound]
return [-1, -1]
# 测试用例
assert Solution().searchRange([5, 7, 7, 8, 8, 10], 8) == [3, 4]
assert Solution().searchRange([5, 7, 7, 8, 8, 10], 6) == [-1, -1]
assert Solution().searchRange([], 0) == [-1, -1]
assert Solution().searchRange([1], 1) == [0, 0]
assert Solution().searchRange([1], 0) == [-1, -1]
assert Solution().searchRange([2, 2], 2) == [0, 1]
assert Solution().searchRange([1, 2, 3, 4, 5], 3) == [2, 2]
# 手动推导 nums=[5,7,7,8,8,10], target=8：
# 找左边界：
# left=0, right=5, mid=2, nums[2]=7 < 8, left=3
# left=3, right=5, mid=4, nums[4]=8 >= 8, right=3
# left=3, right=3, mid=3, nums[3]=8 >= 8, right=2
# left=3 > right=2，退出，left_bound=3
# 找右边界：
# left=0, right=5, mid=2, nums[2]=7 <= 8, left=3
# left=3, right=5, mid=4, nums[4]=8 <= 8, left=5
# left=5, right=5, mid=5, nums[5]=10 > 8, right=4
# left=5 > right=4，退出，right_bound=4
# 检查：nums[3]=8 == target，返回 [3, 4]
# 结果：[3, 4]
|
搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
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
58
59
60
61
62
63
64
65
66
67
|
from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> int:
"""
在旋转排序数组中使用二分查找
思路：
- 旋转排序数组可以看作两个有序数组的拼接
- 二分时，判断 mid 落在哪个有序区间
- 如果 nums[left] <= nums[mid]，说明 [left, mid] 是有序的
- 否则 [mid, right] 是有序的
- 根据 target 是否在有序区间内决定搜索方向
- 时间 O(log n)，空间 O(1)
"""
if not nums:
return -1
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# 判断哪半边是有序的
if nums[left] <= nums[mid]:
# 左半边 [left, mid] 是有序的
if nums[left] <= target < nums[mid]:
# target 在左半边
right = mid - 1
else:
# target 在右半边
left = mid + 1
else:
# 右半边 [mid, right] 是有序的
if nums[mid] < target <= nums[right]:
# target 在右半边
left = mid + 1
else:
# target 在左半边
right = mid - 1
return -1
# 测试用例
assert Solution().search([4, 5, 6, 7, 0, 1, 2], 0) == 4
assert Solution().search([4, 5, 6, 7, 0, 1, 2], 3) == -1
assert Solution().search([1], 0) == -1
assert Solution().search([1], 1) == 0
assert Solution().search([4, 5, 6, 7, 0, 1, 2], 7) == 3
assert Solution().search([4, 5, 6, 7, 0, 1, 2], 4) == 0
assert Solution().search([4, 5, 6, 7, 0, 1, 2], 2) == 6
# 手动推导 nums=[4,5,6,7,0,1,2], target=0：
# left=0, right=6, mid=3, nums[3]=7
# nums[0]=4 <= nums[3]=7，左半边有序
# target=0 不在 [4,7) 范围内，左=mid+1=4
# left=4, right=6, mid=5, nums[5]=1
# nums[4]=0 <= nums[5]=1，左半边有序
# target=0 在 [0,1) 范围内，右=mid-1=4
# left=4, right=4, mid=4, nums[4]=0
# nums[4]==0，找到！返回 4
# 结果：4
|
寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
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
|
from typing import List
class Solution:
def findMin(self, nums: List[int]) -> int:
"""
使用二分查找找到旋转排序数组中的最小值
思路：
- 旋转排序数组的最小值位于"断点"处
- 二分时，如果 nums[mid] > nums[right]，说明最小值在右半边
- 如果 nums[mid] < nums[right]，说明最小值在左半边（包括 mid）
- 使用 nums[right] 作为比较基准，因为旋转后右半边一定比左半边小（或等于）
- 时间 O(log n)，空间 O(1)
"""
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
# 如果中点值大于右端点值，最小值一定在右半边
if nums[mid] > nums[right]:
left = mid + 1
else:
# nums[mid] <= nums[right]，最小值在左半边或就是 mid
right = mid
# 循环结束时，left == right，指向最小值
return nums[left]
# 测试用例
assert Solution().findMin([3, 4, 5, 1, 2]) == 1
assert Solution().findMin([4, 5, 6, 7, 0, 1, 2]) == 0
assert Solution().findMin([11, 13, 15, 17]) == 11
assert Solution().findMin([2, 1]) == 1
assert Solution().findMin([1]) == 1
assert Solution().findMin([2, 3, 4, 5, 1]) == 1
# 手动推导 nums=[3,4,5,1,2]：
# left=0, right=4, mid=2, nums[2]=5
# 5 > 2, left=mid+1=3
# left=3, right=4, mid=3, nums[3]=1
# 1 <= 2, right=mid=3
# left=3, right=3，退出
# 返回 nums[3]=1
# 结果：1
|
寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
from typing import List
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
"""
使用二分查找在两个有序数组中找第 k 小的元素
思路：
- 核心思想：找第 k 小的元素（k = (m+n+1)//2 或 (m+n+2)//2）
- 每次排除 k/2 个元素
- 使用两个指针分别在两个数组中移动
- 找中位数就是找第 (m+n+1)//2 和 (m+n+2)//2 小的元素
- 时间 O(log(m+n))，空间 O(1)
也可以用划分数组的方法：
- 将两个数组分别划分，使左边元素个数等于右边
- 保证 max(left) <= min(right)
- 中位数由左右边界元素决定
"""
def find_kth(k: int) -> float:
"""找到两个数组中第 k 小的元素（k 从 1 开始）"""
idx1, idx2 = 0, 0
while True:
# 边界情况处理
if idx1 == len(nums1):
# nums1 已遍历完，直接从 nums2 取
return nums2[idx2 + k - 1]
if idx2 == len(nums2):
# nums2 已遍历完，直接从 nums1 取
return nums1[idx1 + k - 1]
if k == 1:
# 找最小的，取两个数组当前元素的较小值
return min(nums1[idx1], nums2[idx2])
# 正常情况：比较两个数组中第 k/2 个元素
new_idx1 = min(idx1 + k // 2 - 1, len(nums1) - 1)
new_idx2 = min(idx2 + k // 2 - 1, len(nums2) - 1)
pivot1 = nums1[new_idx1]
pivot2 = nums2[new_idx2]
if pivot1 <= pivot2:
# 排除 nums1 中 idx1 到 new_idx1 的元素
k -= (new_idx1 - idx1 + 1)
idx1 = new_idx1 + 1
else:
# 排除 nums2 中 idx2 到 new_idx2 的元素
k -= (new_idx2 - idx2 + 1)
idx2 = new_idx2 + 1
m, n = len(nums1), len(nums2)
left_k = (m + n + 1) // 2 # 第 k 小的元素
right_k = (m + n + 2) // 2 # 第 k 大的元素
# 中位数是两个中间元素的平均值
return (find_kth(left_k) + find_kth(right_k)) / 2
# 测试用例
assert Solution().findMedianSortedArrays([1, 3], [2]) == 2.0
assert Solution().findMedianSortedArrays([1, 2], [3, 4]) == 2.5
assert Solution().findMedianSortedArrays([0, 0], [0, 0]) == 0.0
assert Solution().findMedianSortedArrays([], [1]) == 1.0
assert Solution().findMedianSortedArrays([2], []) == 2.0
assert Solution().findMedianSortedArrays([1, 3, 5, 7], [2, 4, 6, 8]) == 4.5
# 手动推导 nums1=[1,3], nums2=[2]：
# m=2, n=1, 总长度=3
# left_k = (2+1+1)//2 = 2, right_k = (2+1+2)//2 = 2
# 只需要找第 2 小的元素
# find_kth(2):
# idx1=0, idx2=0, k=2
# k!=1, 比较 nums1[min(0+0,1)]=1 和 nums2[min(0+0,1)]=2
# 1 <= 2, k -= (0-0+1) = 1, idx1 = 1
# k=1, 返回 min(nums1[1]=3, nums2[0]=2) = 2
# 返回 2/1 = 2.0
# 结果：2.0
|
栈
有效的括号
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
输入：s = “()”
输出：true
s 仅由括号 ‘()[]{}’ 组成
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
|
class Solution:
def isValid(self, s: str) -> bool:
"""
使用栈判断括号是否匹配
思路：
- 遍历字符串中的每个字符
- 如果是左括号，压入栈中
- 如果是右括号，检查栈顶是否有匹配的左括号
- 匹配则弹出栈顶，否则返回 False
- 最后检查栈是否为空
- 时间 O(n)，空间 O(n)
"""
stack = []
# 左括号到右括号的映射
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
# 是右括号，检查栈顶
top = stack.pop() if stack else '#'
if mapping[char] != top:
return False
else:
# 是左括号，压入栈中
stack.append(char)
# 栈为空说明所有括号都匹配
return not stack
# 测试用例
assert Solution().isValid("()") == True
assert Solution().isValid("()[]{}") == True
assert Solution().isValid("(]") == False
assert Solution().isValid("([])") == True
assert Solution().isValid("([)]") == False
assert Solution().isValid("{[]}") == True
assert Solution().isValid("") == True
assert Solution().isValid("(") == False
assert Solution().isValid(")") == False
# 手动推导 "(])"：
# 遍历 '(' -> 栈: ['(']
# 遍历 ')' -> 是右括号，栈顶'('匹配，弹出 -> 栈: []
# 遍历 ']' -> 是右括号，栈空，# != '['，返回 False
# 结果：False
# 手动推导 "([])"：
# 遍历 '(' -> 栈: ['(']
# 遍历 '[' -> 栈: ['(', '[']
# 遍历 ']' -> 栈顶'['匹配，弹出 -> 栈: ['(']
# 遍历 ')' -> 栈顶'('匹配，弹出 -> 栈: []
# 栈为空，返回 True
# 结果：True
|
最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素 val 推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
输入：
[“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.
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
58
59
60
|
class MinStack:
"""
最小栈：在常数时间内获取最小元素的栈
思路：
- 使用两个栈：主栈和最小栈
- 主栈：存储所有元素
- 最小栈：存储当前最小元素
- push 时：如果元素 <= 最小栈顶，也压入最小栈
- pop 时：如果元素等于最小栈顶，最小栈也弹出
- getMin：返回最小栈顶
- 所有操作都是 O(1)
"""
def __init__(self):
self.stack = [] # 主栈
self.min_stack = [] # 最小栈
def push(self, val: int) -> None:
"""将元素推入栈"""
self.stack.append(val)
# 如果最小栈为空，或者当前值 <= 最小值，入栈
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
"""弹出栈顶元素"""
if self.stack:
val = self.stack.pop()
# 如果弹出的值等于当前最小值，最小栈也要弹出
if self.min_stack and val == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
"""获取栈顶元素"""
return self.stack[-1] if self.stack else None
def getMin(self) -> int:
"""获取最小元素"""
return self.min_stack[-1] if self.min_stack else None
# 测试用例
minStack = MinStack()
minStack.push(-2) # stack: [-2], min_stack: [-2]
minStack.push(0) # stack: [-2,0], min_stack: [-2]
minStack.push(-3) # stack: [-2,0,-3], min_stack: [-2,-3]
assert minStack.getMin() == -3 # --> 返回 -3
minStack.pop() # stack: [-2,0], min_stack: [-2]
assert minStack.top() == 0 # --> 返回 0
assert minStack.getMin() == -2 # --> 返回 -2
# 手动推导操作序列：
# push(-2): stack=[-2], min_stack=[-2]
# push(0): stack=[-2,0], min_stack=[-2]（0 > -2，不入最小栈）
# push(-3): stack=[-2,0,-3], min_stack=[-2,-3]（-3 <= -2，需要入最小栈）
# getMin: 返回 min_stack[-1] = -3
# pop: val=-3, stack=[-2,0], val == min_stack[-1]，min_stack弹出 -> min_stack=[-2]
# top: 返回 stack[-1] = 0
# getMin: 返回 min_stack[-1] = -2
|
字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
测试用例保证输出的长度不会超过 105。
输入：s = “3[a]2[bc]”
输出：“aaabcbc”
s 由小写英文字母、数字和方括号 ‘[]’ 组成
s 保证是一个 有效 的输入。
s 中所有整数的取值范围为 [1, 300]
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
58
59
60
61
62
63
|
class Solution:
def decodeString(self, s: str) -> str:
"""
使用两个栈解码字符串
思路：
- 使用两个栈：数字栈和字符串栈
- 遇到数字：解析完整的数字
- 遇到 '['：将当前的字符串和数字入栈，开始新的解码
- 遇到字母：追加到当前字符串
- 遇到 ']'：弹出数字栈，重复当前字符串，追加到栈顶字符串
- 时间 O(n)，空间 O(n)
"""
num_stack = [] # 存储重复次数
str_stack = [] # 存储之前的字符串
current_str = "" # 当前正在构建的字符串
num = 0 # 当前解析的数字
for char in s:
if char.isdigit():
# 解析数字（可能是多位）
num = num * 10 + int(char)
elif char == '[':
# 开始新的编码段
# 将当前字符串和数字入栈
str_stack.append(current_str)
num_stack.append(num)
# 重置
current_str = ""
num = 0
elif char == ']':
# 结束当前编码段
# 弹出重复次数
repeat_times = num_stack.pop()
# 弹出之前的字符串
prev_str = str_stack.pop()
# 重复当前字符串，并追加到之前的字符串
current_str = prev_str + current_str * repeat_times
else:
# 字母字符，追加到当前字符串
current_str += char
return current_str
# 测试用例
assert Solution().decodeString("3[a]2[bc]") == "aaabcbc"
assert Solution().decodeString("3[a2[c]]") == "accaccacc"
assert Solution().decodeString("2[abc]3[cd]ef") == "abcabccdcdcdef"
assert Solution().decodeString("abc3[cd]xyz") == "abccdcdcdxyz"
assert Solution().decodeString("a") == "a"
assert Solution().decodeString("10[a]") == "a" * 10
# 手动推导 "3[a2[c]]"：
# char='3': num=3
# char='[': str_stack=[""], num_stack=[3], current_str="", num=0
# char='a': current_str="a"
# char='2': num=2
# char='[': str_stack=["", "a"], num_stack=[3, 2], current_str="", num=0
# char='c': current_str="c"
# char=']': repeat_times=2, prev_str="a", current_str="a"+"c"*2="acc"
# char=']': repeat_times=3, prev_str="", current_str=""+"acc"*3="accaccacc"
# 结果："accaccacc"
|
每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
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
|
from typing import List
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
"""
使用单调递减栈找到下一个更高温度的距离
思路：
- 维护一个存储索引的单调递减栈
- 栈中存储的是尚未找到更高温度的日期索引
- 当遇到比栈顶温度更高的日子，计算距离
- 每个元素最多入栈出栈一次，时间 O(n)，空间 O(n)
"""
n = len(temperatures)
result = [0] * n # 初始化为0，表示没有更高温度
stack = [] # 存储索引，栈底到栈顶对应温度递减
for i, temp in enumerate(temperatures):
# 如果当前温度比栈顶温度高，说明栈顶日期等到了更高温度
while stack and temperatures[stack[-1]] < temp:
prev_idx = stack.pop()
result[prev_idx] = i - prev_idx
# 将当前日期索引入栈
stack.append(i)
return result
# 测试用例
assert Solution().dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]) == [1, 1, 4, 2, 1, 1, 0, 0]
assert Solution().dailyTemperatures([30, 40, 50, 60]) == [1, 1, 1, 0]
assert Solution().dailyTemperatures([30, 60, 90]) == [1, 1, 0]
assert Solution().dailyTemperatures([70, 60, 50, 60]) == [0, 1, 0, 0]
assert Solution().dailyTemperatures([100]) == [0]
# 手动推导 [73,74,75,71,69,72,76,73]：
# i=0, temp=73: stack=[], 入栈 -> stack=[0]
# i=1, temp=74: 74>73(栈顶), 弹出0, result[0]=1, stack=[], 入栈 -> stack=[1]
# i=2, temp=75: 75>74(栈顶), 弹出1, result[1]=1, stack=[], 入栈 -> stack=[2]
# i=3, temp=71: 71<75, 入栈 -> stack=[2,3]
# i=4, temp=69: 69<71, 入栈 -> stack=[2,3,4]
# i=5, temp=72: 72>69(栈顶), 弹出4, result[4]=1
# 72>71(栈顶), 弹出3, result[3]=2
# 72<75, 入栈 -> stack=[2,5]
# i=6, temp=76: 76>72(栈顶), 弹出5, result[5]=1
# 76>75(栈顶), 弹出2, result[2]=4
# 76<... 无栈顶, 入栈 -> stack=[6]
# i=7, temp=73: 73<76, 入栈 -> stack=[6,7]
# 结果：[1,1,4,2,1,1,0,0]
|
柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
from typing import List
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
"""
使用单调递增栈找到最大矩形面积
思路：
- 维护一个存储索引的单调递增栈
- 栈中存储的是高度递增的柱子索引
- 当遇到比栈顶更低的柱子时，弹出栈顶，计算以其为高的矩形面积
- 关键：栈中的每个柱子，左右第一个比它低的索引决定了最大宽度
- 时间 O(n)，空间 O(n)
图解单调栈计算过程：
对于高度数组 [2,1,5,6,2,3]
我们需要找到每个位置作为最矮柱子时的最大矩形
核心思想：
- 对于每个高度 h，它能形成的最大矩形是向左右扩展直到遇到更低的柱子
- 用单调递增栈记录索引
- 当遇到更低的柱子时，弹出栈顶，计算以其为高的矩形
"""
n = len(heights)
stack = [] # 存储索引，栈中对应的高度单调递增
max_area = 0
for i in range(n):
# 当栈不为空且当前高度比栈顶高度低时
# 说明栈顶高度在位置 i 无法继续扩展
while stack and heights[stack[-1]] > heights[i]:
height = heights[stack.pop()] # 栈顶柱子的高度
# 计算宽度：
# - 左边界：栈中新的栈顶索引 + 1（如果栈非空）
# - 右边界：i - 1（当前位置 - 1）
# - 宽度 = 右边界 - 左边界 + 1
if stack:
width = i - stack[-1] - 1
else:
width = i # 栈为空时，左边界是 0
max_area = max(max_area, height * width)
# 将当前索引入栈
stack.append(i)
# 处理栈中剩余的柱子（它们的右边界是数组末尾）
while stack:
height = heights[stack.pop()]
if stack:
width = n - stack[-1] - 1
else:
width = n # 栈为空时，左边界是 0
max_area = max(max_area, height * width)
return max_area
# 测试用例
assert Solution().largestRectangleArea([2, 1, 5, 6, 2, 3]) == 10
assert Solution().largestRectangleArea([2, 4]) == 4
assert Solution().largestRectangleArea([]) == 0
assert Solution().largestRectangleArea([1]) == 1
assert Solution().largestRectangleArea([2, 2]) == 4
assert Solution().largestRectangleArea([5, 4, 3, 2, 1]) == 9 # 最大矩形是整个宽度 * 最小高度1
# 手动推导 [2,1,5,6,2,3]：
# i=0, h=2: stack=[], 入栈 -> stack=[0]
# i=1, h=1: 1<2，弹出0，height=2，width=1（栈空），area=2 -> max=2
# 入栈 -> stack=[1]
# i=2, h=5: 5>1，入栈 -> stack=[1,2]
# i=3, h=6: 6>5，入栈 -> stack=[1,2,3]
# i=4, h=2: 2<6，弹出3，height=6，width=1，area=6 -> max=6
# 2<5，弹出2，height=5，width=2，area=10 -> max=10
# 2>1，入栈 -> stack=[1,4]
# i=5, h=3: 3>2，入栈 -> stack=[1,4,5]
# 处理剩余：弹出5，height=3，width=1，area=3
# 弹出4，height=2，width=4（n=6, stack=[1]），area=8
# 弹出1，height=1，width=6（栈空），area=6
# 结果：max=10
|
堆
数组中的第 K 个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
输入: [3,2,1,5,6,4], k = 2
输出: 5
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
|
import heapq
from typing import List
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
"""
使用最小堆维护K个最大元素
思路：
- 维护一个大小为K的最小堆
- 遍历数组，堆大小小于K时直接入堆
- 当堆大小等于K时，如果当前元素大于堆顶（当前第K大的最小值），则替换
- 堆顶始终是第K大的元素
- 时间 O(n log k)，空间 O(k)
进阶：可以用快速选择算法，平均 O(n)，最坏 O(n²)
"""
# 创建最小堆
heap = []
for num in nums:
if len(heap) < k:
# 堆未满，直接入堆
heapq.heappush(heap, num)
elif num > heap[0]:
# 当前元素比堆顶大，替换堆顶（保持堆中都是较大的元素）
heapq.heapreplace(heap, num)
# 堆顶就是第K大的元素
return heap[0]
# 测试用例
assert Solution().findKthLargest([3, 2, 1, 5, 6, 4], 2) == 5
assert Solution().findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4
assert Solution().findKthLargest([1], 1) == 1
assert Solution().findKthLargest([5, 5, 5, 5, 5], 1) == 5
assert Solution().findKthLargest([7, 7, 7, 7, 7], 3) == 7
# 手动推导 nums=[3,2,1,5,6,4], k=2：
# 遍历3: heap=[], len<2, push(3) -> heap=[3]
# 遍历2: heap=[3], len<2, push(2) -> heap=[2,3]
# 遍历1: heap=[2,3], len=2, 1<=2(堆顶), 不变 -> heap=[2,3]
# 遍历5: heap=[2,3], len=2, 5>2(堆顶), replace -> heap=[3,5]
# 遍历6: heap=[3,5], len=2, 6>3(堆顶), replace -> heap=[5,6]
# 遍历4: heap=[5,6], len=2, 4<=5(堆顶), 不变 -> heap=[5,6]
# 返回 heap[0]=5
# 结果：5
|
前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
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
|
import heapq
from typing import List
from collections import Counter
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
"""
统计频率后使用最小堆找前K个高频元素
思路：
- 先用 Counter 统计每个元素出现的频率
- 创建 (频率, 元素) 的元组列表
- 使用最小堆维护频率最高的K个元素
- 堆顶是K个中最小的频率
- 时间 O(n log k)，优于 O(n log n)
- 空间 O(n) 用于存储频率
"""
# 统计频率
freq = Counter(nums)
# 创建 (频率, 元素) 的元组列表
# Python 的 heapq 是最小堆，所以频率取负数变为最大堆
heap = [(-count, num) for num, count in freq.items()]
# 将列表转换为堆
heapq.heapify(heap)
# 取出前K个高频元素
result = []
for _ in range(k):
count, num = heapq.heappop(heap)
result.append(num)
return result
# 测试用例
assert Solution().topKFrequent([1, 1, 1, 2, 2, 3], 2) == [1, 2]
assert Solution().topKFrequent([1], 1) == [1]
assert set(Solution().topKFrequent([1, 1, 1, 2, 2, 3, 3, 3], 2)) == {1, 3}
assert Solution().topKFrequent([1, 2], 2) == [1, 2]
assert Solution().topKFrequent([4, 4, 4, 2, 2, 3, 1], 2) == [4, 2]
# 手动推导 nums=[1,1,1,2,2,3], k=2：
# 统计频率: {1:3, 2:2, 3:1}
# 创建堆: [(-3,1), (-2,2), (-1,3)] -> heapify
# 弹出第1个: (-3, 1), result=[1]
# 弹出第2个: (-2, 2), result=[1, 2]
# 结果：[1, 2]
|
数据流的中位数
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
输入
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
import heapq
class MedianFinder:
"""
数据流中位数：使用两个堆维护中位数
思路：
- 使用两个堆：最大堆（存较小的一半）和最小堆（存较大的一半）
- max_heap：存较小的一半，堆顶是最大值，用负数实现最大堆
- min_heap：存较大的一半，堆顶是最小值
- 保持 max_heap 元素个数 >= min_heap 元素个数（差不超过1）
- 中位数：
- 如果两个堆大小相同，取两个堆顶的平均值
- 如果 max_heap 多一个，取 max_heap 堆顶
- 所有操作 O(log n)
"""
def __init__(self):
self.max_heap = [] # 最大堆，存较小的一半（用负数实现）
self.min_heap = [] # 最小堆，存较大的一半
def addNum(self, num: int) -> None:
"""
添加一个数字到数据结构中
"""
# 先放入最大堆
heapq.heappush(self.max_heap, -num)
# 平衡：将最大堆的堆顶（最大值）移到最小堆
heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
# 确保 max_heap 元素个数 >= min_heap 元素个数
if len(self.min_heap) > len(self.max_heap):
heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
def findMedian(self) -> float:
"""
返回当前数据流的中位数
"""
if len(self.max_heap) > len(self.min_heap):
# max_heap 多一个，直接返回堆顶
return -self.max_heap[0]
else:
# 两个堆大小相同，返回平均
return (-self.max_heap[0] + self.min_heap[0]) / 2
# 测试用例
mf = MedianFinder()
mf.addNum(1) # arr = [1]
mf.addNum(2) # arr = [1, 2]
assert mf.findMedian() == 1.5 # (1 + 2) / 2
mf.addNum(3) # arr = [1, 2, 3]
assert mf.findMedian() == 2.0
mf2 = MedianFinder()
mf2.addNum(6)
assert mf2.findMedian() == 6.0
# 手动推导 add(1), add(2), findMedian()：
# add(1):
# max=[-1], min=[]
# 移动: max=[], min=[1]
# 平衡: len(min)=1 > len(max)=0, 移动: max=[-1], min=[]
# 状态: max=[-1], min=[] # max存1
#
# add(2):
# max=[-1,-2], min=[] # max存1,2
# 移动: max=[-2], min=[1] # pop返回-1(对应1)，push 1到min
# 平衡: len(min)=1 == len(max)=1, 不需要移动
# 状态: max=[-2], min=[1] # max存2，min存1
#
# findMedian: len(max)=1 == len(min)=1
# 返回 (-(-2) + 1) / 2 = (2 + 1) / 2 = 1.5
# 结果：1.5
# 继续 add(3):
# max=[-2,-3], min=[1] # max存2,3，min存1
# 移动: max=[-3], min=[1,2] # pop返回-2(对应2)，push 2到min
# 平衡: len(min)=2 > len(max)=1, 移动: max=[-2,-3], min=[1] # pop(min)返回1，push -1到max
# 状态: max=[-2,-3], min=[1] # max存2,3，min存1
#
# findMedian: len(max)=2 > len(min)=1
# 返回 -(-2) = 2
# 结果：2.0
|
记录生活