数组下一个更大元素问题：求O(n)时间复杂度最优解法

当然有！咱们可以用单调栈来实现O(n)时间复杂度的解法，这是处理这类「下一个更大元素」问题的经典思路，比双重循环高效太多了。

先聊聊你当前的实现：双重循环的逻辑是对的，但时间复杂度是O(n²)——数组越大，这个方法的效率下降得越明显。另外你的代码还有个小疏漏：只处理了前len(a)-1个元素，最后一个元素30没有被处理，按照逻辑它没有下一个更大元素，应该补充对应的结果（比如用-1表示）。

单调栈的核心是用栈来记录还没找到下一个更大值的元素索引，遍历数组时一次性完成所有元素的匹配，每个元素只会入栈和出栈各一次，所以整体时间复杂度是O(n)。

具体步骤： #

• 初始化一个空栈，用来存数组元素的索引（存索引比存值更方便定位结果的位置）。
• 初始化结果数组array2，长度和原数组一致，默认值设为-1（代表没有下一个更大元素）。
• 遍历原数组的每个元素：
  • 当栈不为空，且当前元素大于栈顶索引对应的元素时：
    • 弹出栈顶索引，把当前元素设为该索引对应位置的下一个更大元素，写入结果数组。
  • 把当前元素的索引压入栈中。

代码实现： #

def next_greater_element():
    array1 = [20, 10, 4, 3, 8, 9, 30]
    array2 = [-1] * len(array1)
    stack = []
    
    for i in range(len(array1)):
        current_num = array1[i]
        # 持续检查栈顶元素，直到当前元素不大于栈顶元素或栈为空
        while stack and current_num > array1[stack[-1]]:
            # 弹出栈顶索引，更新它的下一个更大元素
            top_index = stack.pop()
            array2[top_index] = current_num
        # 将当前索引压入栈，等待后续匹配
        stack.append(i)
    
    print(array2)  # 输出: [30, 20, 8, 8, 9, 30, -1]

next_greater_element()

为什么是O(n)？ #

每个元素只会被压入栈一次、弹出一次，栈的总操作次数是O(n)，加上一次遍历，整体时间复杂度就是O(n)，空间复杂度是O(n)（用来存栈和结果数组）。

小修正：你的示例结果有个小问题 #

你给出的示例结果[30,20,8,4,9,30]里，原数组中值为3的元素（第4个元素）的下一个更大元素应该是8，而不是4——4在3的前面，不算「下一个」后续的更大元素哦～

内容的提问来源于stack exchange，提问作者kkard