使用单调栈优化Python代码的时间复杂度：O(n) 解决方案

第一段引用上面的摘要：本文旨在介绍如何使用单调栈这一数据结构，将原本时间复杂度为O(n²)的Python代码优化至O(n)。通过详细的代码示例和逐步解释，我们将展示如何利用单调栈高效地找到数组中每个元素右侧第一个更大的元素，并将其应用于特定的编码问题，最终实现时间复杂度的显著降低。 **问题背景与优化目标** 原始代码的目标是对一个数字数组进行编码，编码规则是：对于数组中的每个数字，找到它右侧第一个比它大的数字，并将这两个数字相加作为编码后的值。如果右侧没有更大的数字，则保持原值不变。原始代码使用嵌套循环实现，导致时间复杂度为O(n²)，效率较低。我们的目标是找到一种更高效的算法，将时间复杂度降低到O(n)。 **单调栈简介** 单调栈是一种特殊的栈结构，其内部元素保持单调递增或单调递减的顺序。单调栈在解决某些特定问题时非常有效，例如： * 寻找数组中每个元素左/右侧第一个大于/小于它的元素。 * 计算直方图中最大的矩形面积。在本例中，我们将使用单调递减栈来优化编码过程。 **O(n) 解决方案：单调栈的应用** 核心思想是维护一个单调递减栈，栈中存储的是数组元素的索引，而不是元素本身。这样做的好处是可以方便地访问数组元素，并在找到更大的元素时进行更新。以下是使用单调栈优化的Python代码： “`python def encode_array(a): “”” 使用单调栈对数组进行编码，时间复杂度为 O(n)。 Args: a: 待编码的数字数组。 Returns: 编码后的数组。 “”” encoded = a[:] # 创建数组的副本，避免修改原始数组 s = [] # 初始化单调栈 for i, x in enumerate(a): # 栈不为空，并且当前元素大于栈顶元素所对应的数组元素 while s and x > a[s[-1]]: # 弹出栈顶元素，并将其编码为当前元素与栈顶元素所对应的数组元素之和 encoded[s.pop()] += x # 将当前元素的索引压入栈中 s.append(i) return encoded # 示例 a = [4, 3, 7, 3, 2, 8, 6, 1, 10, 3] encoded_array = encode_array(a) print(encoded_array) # 输出：[11, 10, 15, 11, 10, 18, 16, 11, 10, 3]

代码解释：

encode_array(a) 函数： 接收一个数字数组 a 作为输入。
encoded = a[:]： 创建数组 a 的副本，存储编码后的结果。这样做可以避免修改原始数组。
s = []： 初始化一个空栈 s，用于存储数组元素的索引。
for i, x in enumerate(a):： 遍历数组 a，i 是索引，x 是元素值。
while s and x > a[s[-1]]:： 这是一个关键的循环。它检查栈是否为空，以及当前元素 x 是否大于栈顶元素所对应的数组元素 a[s[-1]]。如果满足这两个条件，说明找到了一个比栈顶元素更大的元素。
encoded[s.pop()] += x： 弹出栈顶元素 s[-1]，并将其对应的编码值更新为当前元素 x 与原编码值之和。
s.append(i)： 将当前元素的索引 i 压入栈中，保持栈的单调递减性。
return encoded： 返回编码后的数组。

算法流程

算法从左到右扫描数组。对于每个元素，它会执行以下操作：

如果栈为空，或者当前元素小于等于栈顶元素所对应的数组元素，则将当前元素的索引压入栈中。
如果当前元素大于栈顶元素所对应的数组元素，则不断弹出栈顶元素，直到栈为空，或者当前元素小于等于栈顶元素所对应的数组元素。在弹出每个栈顶元素时，将其对应的编码值更新为当前元素与原编码值之和。最后，将当前元素的索引压入栈中。

时间复杂度分析

虽然代码中包含一个 while 循环，但每个元素最多只会被压入栈一次，也最多只会被弹出栈一次。因此，内层 while 循环的总执行次数不会超过 n。所以，整个算法的时间复杂度为 O(n)。

立即学习“Python免费学习笔记（深入）”；