Lesson 13. 时间复杂度与滚动求最值

1. 时间复杂度简介

时间复杂度 是衡量算法执行效率的重要指标，它描述了随着输入数据量的增大，算法执行时间的增长速度。时间复杂度通常表示为 O(某个函数)，其中 "O" 表示增长的上限。以下介绍四种常见的时间复杂度：O(1)、O(n)、O(n^2) 和 O(n log n)。

常见的时间复杂度

O(1)：常数时间复杂度
操作的执行时间不随输入数据的大小而变化。
例子：从数组中获取第 k 个元素。

Python
arr = [1, 2, 3, 4, 5]
k = 2  # 获取第三个元素（索引从0开始）
element = arr[k]  # O(1)
print(f"Element at index {k}: {element}")

时间复杂度：无论数组大小是多少，获取第 k 个元素所需时间是固定的，属于 O(1)。

O(n)：线性时间复杂度
操作的执行时间随着输入数据量线性增长。
例子：遍历一个数组。

Python
# 假设 arr 是一个已经定义并初始化的列表
arr = [1, 2, 3, 4, 5]
# 使用 for 循环遍历列表
for i in range(len(arr)):
    print(arr[i])

时间复杂度：遍历整个数组需要的时间与数组的长度 n 成正比，属于 O(n)。

O(n^2)：平方时间复杂度
操作的执行时间与输入数据量的平方成正比，常见于双重循环。
例子：打印二维数组中每个元素。

Python
arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for i in range(3):
    for j in range(3):
        print(arr[i][j], end=" ") 
    print()  # 每打印完一行后换行

时间复杂度：双重循环嵌套遍历每个元素，总的执行时间是 n 的平方，属于 O(n^2)。

O(log n)：常见于排序算法（此章节后半部分会详细讲解）
例子：归并排序、快速排序。

Python
def merge(arr, l, m, r):
    # 计算两个子数组的长度
    n1 = m - l + 1
    n2 = r - m

    # 创建临时数组
    L = [0] * n1
    R = [0] * n2

    # 将数据拷贝到临时数组 L[] 和 R[]
    for i in range(n1):
        L[i] = arr[l + i]
    for j in range(n2):
        R[j] = arr[m + 1 + j]

    # 初始化索引
    i = 0  # 左子数组的索引
    j = 0  # 右子数组的索引
    k = l  # 合并后数组的索引

    # 合并临时数组到原数组
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # 拷贝左子数组剩余的元素
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # 拷贝右子数组剩余的元素
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

def mergeSort(arr, l, r):
    # 递归结束条件
    if l >= r:
        return
    # 计算中间点
    m = l + (r - l) // 2
    # 递归排序左半部分
    mergeSort(arr, l, m)
    # 递归排序右半部分
    mergeSort(arr, m + 1, r)
    # 合并已排序的两部分
    merge(arr, l, m, r)

时间复杂度：归并排序通过递归将数组分成更小的部分进行排序，时间复杂度为 O(n log n)。

为什么是 `O(n log n)`?

归并排序是一种 分治算法，我们可以把归并排序的步骤分为两部分：拆分和合并。

1. 拆分过程：递归分解数组

归并排序首先将数组递归地对半拆分，直到每个子数组只剩下一个元素。这个过程类似于构建一棵二叉树，每次将问题的规模减半。

对一个长度为 n 的数组：
第一层：1 个长度为 n 的数组
第二层：2 个长度为 n/2 的数组
第三层：4 个长度为 n/4 的数组
...
第 log n 层：每个数组的长度是 1，共有 n 个数组

因为每次都对数组进行二分，所以整个递归树的深度是 log n。

2. 合并过程：线性合并

当子数组拆分到最小（每个数组只有一个元素）时，归并排序开始合并这些子数组。合并两个有序数组的时间与它们的长度成正比，也就是说合并两个数组的时间是 O(n)。

在递归树的每一层，所有数组的总长度始终是 n，因此：

第一层：合并一个长度为 n 的数组，时间是 O(n)
第二层：合并两个长度为 n/2 的数组，总时间仍然是 O(n)
第三层：合并四个长度为 n/4 的数组，总时间也是 O(n)

无论有多少个小数组，合并每一层的总时间都是 O(n)。

3. 递归树的层数

拆分的过程最多进行 log n 次（每次将数组对半分）。因此，递归树的深度是 log n，即最多有 log n 层。

总时间复杂度的计算

因为每一层的合并时间都是 O(n)，而整个递归树有 log n 层，所以总的时间复杂度是 O(n) * O(log n) = O(n log n)

为什么不会超过 O(n log n)

有人可能会疑惑：既然我们在递归中反复分裂数组，为什么时间复杂度不会超过 O(n log n) 呢？

每层的合并操作是线性的：虽然递归分裂会产生多个小数组，但每一层中所有数组的总长度仍然是 n。也就是说，每一层合并的时间复杂度始终是 O(n)，不会累积更多复杂度。
递归的深度是 log n：由于每次递归都将数组对半分裂，整个递归过程只会进行 log n 次分裂。因此，递归树的深度是 log n。

最终的时间复杂度是每层的时间 O(n) 乘以递归树的层数 log n，所以总时间复杂度是 O(n log n)。

时间复杂度总结
O(1)：执行时间不受输入规模影响。
O(n)：执行时间随输入规模线性增长。
O(n^2)：执行时间与输入规模的平方成正比，通常发生在嵌套循环中。
O(n log n)：常见于高效的排序算法。

具体实例

考虑一个简单的算法：计算数组中所有元素的和。

Python
def sumArray(arr, n):
    total = 0
    for i in range(n):
        total += arr[i]  # 基本操作
    return total

# 定义数组
arr = [1, 2, 3, 4, 5]
n = len(arr)  # 获取数组长度

# 输出数组的和
print("Sum of array:", sumArray(arr, n))

步骤分析

确定基本操作：
- 基本操作是 total += arr[i]。
计算基本操作的次数：
- 在最坏情况下，for 循环会执行 n 次（其中 n 是数组 arr 的长度）。
- 因此，基本操作的次数为 n 。
使用大 O 表示法：
- 所以时间复杂度是 O(n)。
考虑最坏情况：
- 无论输入的具体内容如何，只要数组长度为 n ，基本操作都会执行 n 次，因此最坏情况为 O(n)。
特殊情况：
如果数组为空，循环不会执行，但我们仍然认为时间复杂度为 O(n)，因为我们关注的是输入的规模。

随堂练习

判断以下代码的时间复杂度

Python
def find_max(arr):
    max_num = arr[0]
    for num in arr:  # 基本操作
        if num > max_num:
            max_num = num
    return max_num

# Example usage
arr = [1, 5, 3, 9, 2]
print(f"Max number: {find_max(arr)}")

解答

第一段代码（find_max）：

基本操作是 if num > max_num。
在最坏情况下，循环执行 n 次。
所以时间复杂度是 O(n)。

2. 排序算法与应用

排序是程序设计中一个非常基础但重要的操作。它不仅可以让数据按特定顺序排列，还能帮助我们解决许多与数据处理相关的问题。通过排序，我们可以更快地解决找第 K 大元素、合并重叠区间等问题。

适用场景

排序的应用场景非常广泛，尤其是在数据处理中，你会经常遇到需要对数据进行排序的情况：

找出第 K 大元素：通过排序数据，可以很快找出第 K 大（或第 K 小）的元素。
合并区间：当处理多个区间或段时，常常需要先将这些区间按某个维度排序，然后合并它们。
例子：合并日程、任务时间段等数据，解决区间重叠问题。
优化操作：不同的排序算法在面对不同规模的数据时表现各异，因此选择合适的排序算法对于提高程序性能非常重要。

常用技巧

1. 内置排序函数

大多数编程语言都提供了内置的排序函数，它们经过优化，能以高效的方式进行排序。Python 提供了 list.sort() 方法和 sorted() 函数。

示例代码：

Python
# 定义一个整数列表
nums = [3, 1, 4, 1, 5, 9]

# 使用内置的排序方法对列表进行升序排序（原地排序）
nums.sort()

# 输出排序后的列表
print("Sorted array:", nums)

或者使用 sorted() 函数：

Python
# 定义一个整数列表
nums = [3, 1, 4, 1, 5, 9]

# 使用内置的 sorted() 函数返回一个新的排序后的列表
sorted_nums = sorted(nums)

# 输出排序后的列表
print("Sorted array:", sorted_nums)

说明：

list.sort() 方法会对列表进行原地升序排序，不会创建新的列表。
sorted() 函数会返回一个新的排序后的列表，原列表保持不变。
使用内置的排序方法是非常快捷且高效的，对于大多数简单排序任务，它的效率非常高。

2. 自定义排序

有时我们需要按照自定义的规则对数据进行排序。比如，我们可能希望按列表的某个特定元素进行排序，而不是按默认的顺序。在 Python 中，我们可以通过 sort() 方法或 sorted() 函数的 key 参数来自定义排序规则。

示例代码：

Python
# 定义一个二维列表
data = [[1, 3], [2, 2], [3, 1]]

# 使用自定义的排序规则按第二个元素排序
data.sort(key=lambda x: x[1])

# 输出排序后的二维列表
for row in data:
    print(f"{row[0]}, {row[1]}")

说明：

在这个例子中，我们使用了 sort() 方法的 key 参数，传入了一个匿名函数 lambda x: x[1]，按照每个子列表的第二个元素进行排序。
sort() 方法的 key 参数用于指定排序的依据，lambda 函数可以灵活地定义排序规则。
如果需要返回新的排序列表而不改变原列表，可以使用 sorted() 函数：

Python
sorted_data = sorted(data, key=lambda x: x[1])

使用 `cmp_to_key` 进行复杂排序

除了使用简单的 lambda 函数外，Python 还提供了 functools.cmp_to_key，适用于需要更加复杂排序逻辑的情况。它可以将基于比较函数的逻辑转换为现代的 key 函数，使其可以用于 sorted() 或 sort() 函数。

示例代码

假设我们有一个需要根据自定义规则进行排序的列表。例如，按奇数优先、偶数其次的规则排序，如果两者相同，则按数字大小排序：

Python
from functools import cmp_to_key

# 自定义比较函数
def custom_compare(x, y):
    # 奇数优先，偶数靠后
    if (x % 2 == 1) and (y % 2 == 0):
        return -1
    elif (x % 2 == 0) and (y % 2 == 1):
        return 1
    # 如果同为奇数或偶数，按数字大小排序
    else:
        return (x > y) - (x < y)

# 待排序列表
arr = [3, 1, 4, 1, 5, 9, 2, 6, 8, 7]

# 使用 cmp_to_key 将比较函数转换为 key
sorted_arr = sorted(arr, key=cmp_to_key(custom_compare))

print(sorted_arr)  # 输出: [3, 1, 1, 5, 9, 7, 2, 4, 6, 8]

说明

custom_compare 是自定义的比较函数，按奇偶性排序。如果 x 是奇数而 y 是偶数，则返回 -1，表示 x 应该排在前面；反之，返回 1 表示 y 应该排在前面。对于同类型（奇数或偶数），直接按数字大小排序。
cmp_to_key 将这个比较函数转换为 sorted() 函数的 key 参数，可以使用自定义排序逻辑。
这种方法非常适合当 lambda 无法轻松表达复杂排序逻辑时使用。

3. 排序优化

排序算法在处理不同规模数据时表现各异。以下是一些常见的排序算法及其适用场景，供大家初步了解：

选择排序：适用于小规模数据集，时间复杂度为 O(n²)。特点是每次从未排序部分中选择最小（或最大）的元素，然后将其放到已排序部分的末尾。简单易懂，但性能较差，不适合大数据集。
插入排序：适合于几乎已排序的数据集，时间复杂度也是 O(n²)。当数据几乎有序时，插入排序的效率会比选择排序好得多，因为它减少了不必要的比较和移动。
快速排序：性能较好的通用排序算法，平均时间复杂度为 O(n log n)。通过选择一个基准元素（pivot），将数组划分为两部分，递归地对两部分进行排序。适合大规模数据集，但最坏情况下时间复杂度为 O(n²)。
归并排序：时间复杂度为 O(n log n)，且是稳定的排序算法。将数组不断拆分成子数组，分别排序后再合并。性能稳定，但需要额外的内存空间存储临时数组。
冒泡排序：简单但性能较差的排序算法，时间复杂度为 O(n²)。通过重复遍历列表，比较相邻元素并交换，将较大的元素逐渐移动到列表末尾。适用于非常小规模的数据集。
堆排序：基于堆数据结构的排序算法，时间复杂度为 O(n log n)。通过建立最大堆或最小堆来排序，不需要额外的内存空间。虽然效率和快速排序相当，但在实际应用中常用快速排序。
计数排序：时间复杂度为 O(n + k)，适用于数据范围较小的整数排序。通过统计每个元素出现的次数来排序。当数据范围较小时，性能非常优异，但范围很大时，空间消耗会过高。
桶排序：时间复杂度为 O(n + k)，适合均匀分布的数据集。将数据分到多个桶中，分别对每个桶进行排序，然后合并所有桶中的元素。对于分布均匀的数据，性能很好，但数据分布不均时性能可能下降。
基数排序：非比较排序算法，时间复杂度为 O(n * k)，适用于位数固定的数据。通过按位（如个位、十位）进行多次排序来完成整体排序。适用于对整数或字符串进行排序，尤其是当位数 k 较小时。

此外，Python 的内置排序算法（list.sort() 和 sorted()）使用的是 Timsort，一种结合了归并排序和插入排序的混合算法。它的平均和最坏情况下的时间复杂度都是 O(n log n)，在处理几乎有序的数据时性能非常优秀。

2.1 排序算法例题讲解

2.1.1 LC 215：找出数组中的第 `K` 大元素

题目描述：

给定一个未排序的数组，找出其中第 K 大的元素。

解题思路：

可以先对数组进行降序排序，然后直接返回排好序后的数组中的第 K 个元素。

代码实现：

Python
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 对数组进行降序排序
        nums.sort(reverse=True)
        # 返回第 K 个元素
        return nums[k - 1]

说明：

这里我们通过使用 sort() 方法的 reverse=True 参数，将数组 nums 按照降序排序。
然后直接返回排序后的数组中的第 k-1 个元素，即为第 K 大的元素。

2.2 排序算法举一反三

2.2.1 LC 56：合并区间

题目描述：

给定若干个闭合区间 [x1, y1], [x2, y2], ...，请将所有重叠的区间合并。例如，区间 [1, 3] 和 [2, 6] 可以合并为 [1, 6]。

解题思路：

排序：首先，按照区间的起始值对所有区间进行排序。
合并：遍历每个区间，若当前区间与前一个区间重叠，则合并它们；否则将当前区间直接加入结果列表。

代码实现：

Python
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []

        # 按区间起始位置排序
        intervals.sort(key=lambda x: x[0])

        merged = []

        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                # 如果结果为空或当前区间与上一个区间不重叠，直接加入结果
                merged.append(interval)
            else:
                # 如果重叠，更新最后一个区间的结束位置
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

讲解：

排序：使用 sort() 方法和 key=lambda x: x[0] 按照每个区间的起始值进行升序排序。
遍历区间
如果 merged 为空，或者当前区间的起始值大于 merged 中最后一个区间的结束值，说明没有重叠，直接将当前区间加入 merged。
如果有重叠，更新 merged 中最后一个区间的结束值为两者结束值的最大值。

2.2.2 LC 252：会议室

题目描述：

给定一系列会议时间区间，判断是否能让所有会议无冲突地安排在一间会议室中。

解题思路：

将所有的会议按照开始时间排序，然后遍历每个会议，检查是否有重叠区间。

代码实现：

Python
class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        # 按会议的开始时间进行排序
        intervals.sort(key=lambda x: x[0])

        # 遍历会议，检查是否存在重叠
        for i in range(1, len(intervals)):
            if intervals[i][0] < intervals[i - 1][1]:
                return False  # 存在重叠，无法参加所有会议

        return True  # 无重叠，可以参加所有会议

讲解：

排序会议：使用 sort() 方法按会议的开始时间进行升序排序，方便后续检查。
检查重叠
- 从第二个会议开始，比较当前会议的开始时间和前一个会议的结束时间。
- 如果当前会议的开始时间小于前一个会议的结束时间，说明会议时间有重叠，无法参加所有会议。
- 如果没有发现重叠，返回 True。

2.2.3 LC 347：前 K 个高频元素

题目描述：

给定一个非空的整数数组，返回其中出现频率最高的前 K 个元素。

解题思路：

1 .统计频率：使用哈希表（字典）手动统计每个元素的出现次数。

2.自定义排序：将哈希表中的元素根据其出现频率进行降序排序。

3.提取结果：在排序后的列表中，选取出现频率最高的前 K 个元素并返回。

代码实现：

Python
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
         # 统计每个元素的出现次数
        count = {}
        for num in nums:
            if num in count:
                count[num] += 1
            else:
                count[num] = 1

        # 对字典的 items 进行排序，按照出现频率从高到低排序
        sorted_items = sorted(count.items(), key=lambda x: x[1], reverse=True)

        # 3 选取出现频率最高的前 K 个元素
        result = [item[0] for item in sorted_items[:k]]

        return result

讲解：

统计频率：遍历数组时，使用字典 count 来记录每个元素的出现次数。每当元素出现时，如果该元素已经存在于字典中，则将对应的值加1；如果该元素不存在，则将其初始值设为1。

排序：通过 sorted() 函数对字典中的键值对（即 (元素, 出现次数) 的元组）进行排序，key=lambda x: x[1] 表示按照出现次数（频率）进行排序，reverse=True 表示从高到低排序。

提取元素：在排序后的结果中，提取前 K 个频率最高的元素。这一步通过列表推导式来实现，取出排序结果中的前 K 个元素的键，并将其存入结果列表 result。

3. 贪心算法

贪心算法是一种解决问题的策略，其核心思想是：在解决问题的每一步中，总是选择当前看起来最优的选择，通过一系列这样的局部最优选择，最终希望获得全局最优解。

需要注意的是，贪心算法并不总是能得到全局最优解。它只有在某些特定问题中有效，特别是当问题满足贪心选择性质时。

贪心算法的特点

局部最优选择：
贪心算法在每一步中只做出当前看起来最优的选择，而不关心之后可能发生的情况。它不会考虑这次选择是否会影响后续决策，只看当下哪个选项是最有利的。例如，在分数背包问题中，贪心策略是每次优先选择单位重量价值最高的物品，因为它在当前的选择中带来的收益最大。
- 优点：通过每一步的最优选择，可以快速找到一个可行解。贪心算法的规则简单、直观，易于实现，通常可以通过一次扫描或排序解决问题，时间复杂度较低。例如在分数背包问题中，贪心算法只需要按单位价值排序，时间复杂度为 (O(n log n))。
- 缺点：局部最优解不一定能保证全局最优，因为在一些问题中，最佳的整体方案依赖于多步决策的综合效果，而不是单纯的每一步最优。贪心算法无法通过局部最优解找到全局最优解，尤其在复杂问题（如 0-1 背包问题）中，它可能会陷入次优解。
不可回溯：
贪心算法的一个重要特点是决策不可回头修改。一旦做出某个选择，算法就不会再考虑改变它，即使后续发现这个选择可能不是最优的。因为贪心算法依赖的是当前最优选择的策略，所以它不会为未来的选择留下回旋余地。
- 优点：由于不需要回溯，贪心算法执行速度非常快，时间复杂度通常比需要回溯的算法（如动态规划、回溯法等）更低。贪心算法的高效性体现在其快速、直接的解决思路上，适用于处理大规模问题时的高效求解。
- 缺点：由于贪心算法不具备回溯能力，它只能在符合贪心选择性质的问题中有效。如果问题不满足这种性质，算法可能会在后续步骤中陷入次优解或死胡同，无法达到全局最优解。

具体步骤

贪心算法通常遵循以下基本步骤：

明确贪心策略：确定每一步的局部最优解选择策略。
排序：如果问题涉及多个选择，通常需要对其进行排序（如按结束时间、单位价值等）。
逐步选择：根据贪心策略，按照排序结果逐步选择最优项。
检查可行性：每次选择时，确保当前选择满足问题的约束条件（如不冲突、不超出容量等）。
构造解：将所有的选择组合起来，形成问题的最终解。

贪心算法的适用条件

要判断一个问题是否适合使用贪心算法，可以观察以下特征：

贪心选择性质：在每一步中，选择的局部最优解能够保证不会影响后续选择的最优性，即贪心选择在每一步都能保持全局最优。
无后效性：当前的选择不会影响未来的选择。每个选择的结果只依赖当前状态，而不会依赖之前的决策。即一旦做出了某个选择，该选择就不可改变。

如果问题满足以上两点，那么通常可以使用贪心算法求解。

贪心算法 vs 动态规划的判定标准

在区分一个问题是否适合使用贪心算法或动态规划时，最优子结构和子问题重叠是关键的判定标准：

贪心选择的适用条件：
- 局部最优选择性质：贪心算法每一步做出的选择都是局部最优解，且这些局部最优解构成了全局最优解。这种性质一般存在于可以通过逐步选择解决的简单优化问题。
- 无后效性：未来的决策不依赖于之前的选择，因此一旦做出了选择，不需要回溯检查。例如，分数背包问题，每次选择单位价值最高的物品不会影响之后的选择。
动态规划的适用条件：
- 最优子结构：全局最优解依赖于子问题的最优解。如果每个子问题的解都影响到全局最优解，那么这种问题通常需要使用动态规划来解决。背包问题中的0-1 背包问题就属于此类问题，当前物品是否选入背包会影响未来的选择，因此无法简单通过贪心策略得到最优解。
- 子问题重叠：如果问题可以被拆分为多个子问题，且这些子问题之间存在重叠（即某个子问题的解会多次被使用），那么动态规划是更有效的选择。

总结来看，如果问题可以通过单纯的局部最优选择解决，并且未来的选择不依赖于过去的选择，通常可以使用贪心算法；否则需要通过动态规划来解决问题。

简单例子

1. 分数背包问题（贪心算法）

问题描述：你有一个容量为 50 的背包，和一堆物品，每件物品都有重量和价值。你可以将每件物品按任意比例装入背包（例如可以装入物品的一部分），目标是让背包里的物品总价值最大化。

贪心策略：优先选择单位重量价值最高的物品，尽可能多地装入背包。

分析步骤：

明确贪心策略：每次选择单位重量价值最高的物品，尽可能多装入背包。
排序：将所有物品按照单位重量的价值从高到低排序。
逐步选择：按照排序后的顺序，优先选择单位价值最高的物品，直到背包装满。
检查可行性：每次选择物品时，检查背包剩余容量是否足够。如果容量不足，将物品的一部分装入背包。
构造解：将选入背包的物品组合起来，计算总价值，得到问题的解。

2. 0-1 背包问题（动态规划）

问题描述：你有一个容量为 50 的背包和一堆物品，每件物品都有一个确定的重量和价值。你只能选择将某件物品完全放入背包或者不放入，不能只装一部分。目标是选择一些物品放入背包，使得背包中的物品总价值最大化。

动态规划思路：对于每件物品，你需要决定是否放入背包。每次的选择都依赖于背包当前的容量以及之前的选择。因为选择一次物品会影响到后续能装多少东西，所以我们不能使用贪心算法，而需要通过动态规划来考虑所有可能的组合。

用简单的话来理解动态规划的思路：

状态：我们用 dp[i][w] 表示前 i 个物品在容量为 w 的背包中所能装的最大总价值。换句话说，dp[i][w] 是一个中间结果，告诉我们如果只考虑前 i 个物品，并且背包容量为 w，我们能装的最高价值是多少。
状态转移方程：这个就是动态规划中的“规则”，用来指导我们如何根据前面的计算结果推导出当前的最优解。

对于每件物品 i，你有两种选择：

Text Only
- **不选这件物品**：那么最大价值就是 `dp[i-1][w]`，即背包容量保持不变，前面 i-1 个物品的最优解。
- **选这件物品**：如果选择物品 `i`，则当前的背包容量减少 `weight[i]`，而我们还获得了 `value[i]` 这个物品的价值。所以最大价值变成了 `dp[i-1][w - weight[i]] + value[i]`。

两者取较大值： dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

理解这段公式：
- 如果你不选物品 i，那么你只能依赖前面 i-1 个物品在容量为 w 时的最优解，即 dp[i-1][w]。
- 如果你选了物品 i，那你需要腾出足够的空间来放它，也就是说背包容量会减少 weight[i]，然后你能获得这件物品的价值 value[i]，再加上前 i-1 个物品在减少了的容量 w - weight[i] 时的最优解，即 dp[i-1][w - weight[i]]。
如何求解：我们从空背包开始，逐步增加物品和容量，每次用上面这个公式去更新当前背包容量的最优解。通过这个递推过程，最后就能得到整个背包的最大价值。

举个简单例子：

假设我们有一个背包容量为 5，物品如下：

物品 1：重量 2，价值 3
物品 2：重量 3，价值 4
物品 3：重量 4，价值 5

动态规划表的构建过程：

i\w	2	3	4	5
0	0	0	0	0
1	3	3	3	3
2	3	4	4	7
3	3	4	5	7

当 i = 1（只考虑物品1）：物品1的重量为2，所以当背包容量小于2时，无法放入，价值为0；当容量等于2或大于2时，放入物品1，价值为3。
当 i = 2（考虑前两个物品）：在容量为3时，放入物品2比物品1好，价值为4；当容量为5时，放入物品1和物品2，价值为7。
当 i = 3（考虑三个物品）：物品3太重，不能放入背包，之前的最优值保持不变。

最终，我们得到的最大价值为7。

3. 活动选择问题（贪心算法）

问题：你有一系列活动，每个活动都有开始时间和结束时间。你需要选择尽可能多的活动，并且这些活动不能重叠。

贪心策略：每次选择结束时间最早且不与其他活动冲突的活动。

步骤：

明确贪心策略：每次选择结束时间最早的活动，以留出更多时间给其他活动。
排序：将活动按结束时间从早到晚排序。
逐步选择：从第一个活动开始，依次选择结束时间最早且与之前活动不冲突的活动。
检查可行性：每次选择活动时，检查该活动是否与已经选择的活动冲突。
构造解：将每次选择的活动加入最终解，直到没有活动可以再选。

贪心算法的局限性

贪心算法并不总是能找到最优解。比如：

1. 0-1 背包问题

在这个问题中，你必须选择完整的物品（要么全选，要么不选），而不能选择物品的一部分。如果你使用贪心算法来选择单位价值最高的物品，很可能会因为重量限制而无法选择最优组合。

2. 最短路径问题

在某些图上，贪心策略（总是选择距离最近的节点）并不总能找到最短路径。

总结：

贪心算法是一种简单而高效的策略，适合用在那些可以通过局部最优解得到全局最优解的问题上。它的关键在于每一步都做出最好的局部选择，希望最终得到最优解。虽然并不是所有问题都适合用贪心算法，但在合适的情况下，它能快速找到解。

3.1 贪心算法例题讲解

3.1.1 LC 455: 分发饼干

题目描述：有 g 个孩子和 s 个饼干，每个孩子都有一个贪心指数，表示他最少需要多少饼干。每个饼干都有一个大小，表示它可以满足某个孩子的需求。你要分发尽可能多的饼干给孩子，使得最多的孩子能得到满足。

贪心算法步骤：

排序：将孩子的需求（贪心指数）和饼干的大小都进行升序排序。
这样可以确保我们可以用最小的饼干去满足最小需求的孩子，从而尽可能满足更多的孩子。
匹配：从最小的饼干和最小需求的孩子开始匹配。
每次如果饼干大小可以满足当前孩子的需求，就将这个饼干分配给这个孩子，然后移动到下一个孩子。
如果当前饼干不够满足孩子需求，就继续尝试下一个更大的饼干，直到所有孩子或饼干用完。

代码实现：

Python
class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        # 将孩子的需求和饼干的大小排序
        g.sort()
        s.sort()

        i = 0  # 孩子索引
        j = 0  # 饼干索引

        # 遍历孩子和饼干数组
        while i < len(g) and j < len(s):
            # 如果当前饼干能满足当前孩子
            if s[j] >= g[i]:
                i += 1  # 满足了孩子 i，处理下一个孩子
            j += 1  # 尝试下一个饼干

        return i  # 返回满足的孩子数量

讲解：

排序步骤：
- 首先将孩子的需求数组 g 和饼干大小数组 s 进行排序。排序后，较小的孩子需求和较小的饼干会排列在数组前面，这样可以尽量用最小的饼干去满足最小需求的孩子。
匹配过程：
- 使用两个指针 i 和 j，分别指向孩子和饼干数组的起始位置。
- 当 s[j] >= g[i] 时，表示当前饼干可以满足当前孩子，孩子被满足，移动指针 i，处理下一个孩子。
- 无论是否满足，饼干都会被尝试，所以 j 每次都会移动到下一个饼干。
最终结果：
- 当遍历结束时，i 的值就是能够满足的孩子数量，即最后返回的结果。

3.2 贪心算法举一反三

3.2.1 LC 435: 无重叠区间

题目描述：

给定一组区间，找到最少需要移除的区间数量，使得剩下的区间互不重叠。

贪心算法步骤：

排序：按照区间的结束时间进行升序排序。排序后，我们可以优先选择结束时间较早的区间，这样能够为后续区间留出更多空间，减少冲突。
选择区间：每次选择结束时间最早且不与前一个选择的区间重叠的区间。如果当前区间的开始时间小于前一个区间的结束时间，说明发生了重叠，我们就需要移除当前区间。否则，我们更新当前区间为新的结束时间，并继续处理下一个区间。

代码实现：

Python
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        # 按结束时间排序
        intervals.sort(key=lambda x: x[1])

        count = 0
        end = intervals[0][1]

        for i in range(1, len(intervals)):
            if intervals[i][0] < end:
                count += 1  # 有重叠，需要移除
            else:
                end = intervals[i][1]  # 更新结束时间

        return count

讲解：

排序步骤：
- 按区间的结束时间对所有区间进行排序。排序后的区间按结束时间从小到大排列，这样可以确保每次选择的区间结束得最早，能够尽量避免后续区间与其发生重叠。
遍历选择区间：
- 初始化一个 end 变量，表示已选定区间的结束时间。遍历剩余区间时，检查每个区间的开始时间是否与当前选定的结束时间发生重叠。
- 如果当前区间的开始时间小于 end，说明发生了重叠，必须移除当前区间，count 加 1。
- 如果没有重叠，则更新 end 为当前区间的结束时间。
返回结果：
- count 记录了被移除的区间数，遍历结束后，返回这个移除的区间数。

3.2.2 LC 605: 种花问题

题目描述：

给定一个表示花坛的整数数组 flowerbed，其中 flowerbed[i] = 0 表示该位置是空的，flowerbed[i] = 1 表示该位置已经种了花。花坛中花不能种在相邻的地块上，问是否能够在不违反规则的情况下再种下 n 朵花。

贪心算法步骤：

遍历花坛：从左到右依次检查每个位置。如果当前位置是空的 0，并且它的前一个位置和后一个位置也是空的（如果存在），那么可以在这个位置种花。
计数并跳过相邻位置：每次成功种花后，增加计数，并跳过下一个位置，因为相邻的位置不能种花。

代码实现：

Python
class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        count = 0  # 记录可以种花的数量
        i = 0
        length = len(flowerbed)

        while i < length:
            if flowerbed[i] == 0:
                prev_empty = (i == 0) or (flowerbed[i - 1] == 0)
                next_empty = (i == length - 1) or (flowerbed[i + 1] == 0)
                if prev_empty and next_empty:
                    flowerbed[i] = 1  # 种花
                    count += 1
                    if count >= n:
                        return True
                    i += 1  # 跳过下一个位置
            i += 1  # 移动到下一个位置
        return count >= n  # 检查是否种够 n 朵花

讲解：

遍历判断能否种花：
遍历整个花坛，检查每个位置是否可以种花。当前位置必须满足三个条件才能种花：
- 当前为 0，即空地。
- 前一个位置为 0 或者是花坛的起始位置。
- 后一个位置为 0 或者是花坛的末尾位置。
种花后跳过相邻位置：
- 每次成功种花后，需要跳过下一个位置，避免相邻种花。
提前终止：
- 如果在遍历过程中已经种够了 n 朵花，则可以提前返回 True。

3.2.3 LC 1029: 两地调度

题目描述：

有 2N 个人，每个人都需要飞往 A 市或 B 市。给定一个 costs 数组，其中 costs[i] = [aCost, bCost] 表示第 i 个人飞往 A 市的费用和飞往 B 市的费用。现在需要把这些人分配到两个城市，使得 N 个人飞往 A 市，N 个人飞往 B 市，要求总费用最小。

贪心算法步骤：

计算成本差异：计算每个人去 A 市和 B 市的费用差，即 aCost - bCost。我们希望优先让那些去 A 市更便宜的人去 A 市，去 B 市更便宜的人去 B 市。
排序选择：根据费用差进行排序。差异越大的人，意味着去 A 市更划算；差异越小甚至为负，意味着去 B 市更划算。
分配城市：前 N 个人安排到 A 市，后 N 个人安排到 B 市，最终得到最小的总费用。

代码实现：

Python
class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        # 按照 aCost - bCost 升序排序
        costs.sort(key=lambda x: x[0] - x[1])

        totalCost = 0
        n = len(costs) // 2

        # 前 N 个人去 A 市
        for i in range(n):
            totalCost += costs[i][0]

        # 后 N 个人去 B 市
        for i in range(n, 2 * n):
            totalCost += costs[i][1]

        return totalCost

讲解：

计算成本差异：
- 每个人都有去 A 市和 B 市的两种选择，通过 aCost - bCost 来衡量去哪个城市更划算。
排序步骤：
- 根据 aCost - bCost 对 costs 数组进行排序，差值小的（去 B 市更划算）排在后面。
分配城市：
- 排序后，前一半的人（去 A 市更划算）分配到 A 市，后一半的人（去 B 市更划算）分配到 B 市。
返回结果：
- 最终返回总的费用，即前 N 个人的 A 市费用和后 N 个人的 B 市费用之和。

4. 课后练习

排序问题

题目编号	题目名称	简介
LC1288	删除被覆盖的区间	给定一组区间，找出其中未被覆盖的区间，移除被覆盖的区间。
LC1024	视频拼接	给定一组区间，判断是否能够通过拼接区间覆盖整个视频长度。
LC763	划分字母区间	给定一个字符串，将其划分为尽可能多的不重叠的区间，使得每个字母最多出现在一个区间中。
LC57	插入区间	给定一组非重叠的区间和一个新的区间，将新区间插入并合并所有可能的重叠区间。
LC179	最大数	给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

贪心算法问题

题目编号	题目名称	简介
LC121	买卖股票的最佳时机	给定股票价格，找到在最佳时机买入和卖出以获得最大利润。
LC122	买卖股票的最佳时机 II	允许多次买卖，找到在最佳时机买入和卖出以获得最大利润。
LC55	跳跃游戏	给定一个数组，判断是否能跳到数组的最后一个位置。
LC45	跳跃游戏 II	给定一个数组，找到跳到数组最后一个位置的最少跳跃次数。
LC409	最长回文串	给定一个字符串，找到其中能组成的最长回文串的长度。

Lesson 13. 时间复杂度与滚动求最值

目录

1. 时间复杂度简介

常见的时间复杂度

为什么是 O(n log n)?

时间复杂度总结

具体实例

步骤分析

随堂练习

判断以下代码的时间复杂度

解答

2. 排序算法与应用

适用场景

常用技巧

1. 内置排序函数

2. 自定义排序

使用 cmp_to_key 进行复杂排序

示例代码

说明

3. 排序优化

2.1 排序算法例题讲解

2.1.1 LC 215：找出数组中的第 K 大元素

题目描述：

解题思路：

代码实现：

2.2 排序算法举一反三

2.2.1 LC 56：合并区间

题目描述：

解题思路：

代码实现：

2.2.2 LC 252：会议室

题目描述：

解题思路：

代码实现：

讲解：

2.2.3 LC 347：前 K 个高频元素

题目描述：

解题思路：

代码实现：

讲解：

3. 贪心算法

贪心算法的特点

具体步骤

贪心算法的适用条件

贪心算法 vs 动态规划的判定标准

简单例子

1. 分数背包问题（贪心算法）

分析步骤：

2. 0-1 背包问题（动态规划）

用简单的话来理解动态规划的思路：

举个简单例子：

3. 活动选择问题（贪心算法）

贪心算法的局限性

1. 0-1 背包问题

2. 最短路径问题

总结：

3.1 贪心算法例题讲解

3.1.1 LC 455: 分发饼干

代码实现：

讲解：

3.2 贪心算法举一反三

3.2.1 LC 435: 无重叠区间

代码实现：

3.2.2 LC 605: 种花问题

代码实现：

3.2.3 LC 1029: 两地调度

代码实现：

4. 课后练习

排序问题

贪心算法问题

为什么是 `O(n log n)`?

使用 `cmp_to_key` 进行复杂排序

2.1.1 LC 215：找出数组中的第 `K` 大元素