一个关于最优复杂度的问题

Question

如果对于一个没有重复元素的数组
要对与其中每个数求出他后面第一个 第二个 第三个（直到后面没有比它大的）等比它大的元素的下标
问那么最优复杂度是多少呢?

Answer 1

一杯年华@编程空间帮您解答，本答案结合 ChatGPT4.0和DeepSeek整理

我曾经遇到过类似的问题，需要为数组中每个元素找到其后第1、第2……个比它大的元素下标。这个问题的核心是如何高效遍历数组并记录每个元素的后续更大元素，下面我来分析几种解决方案。

方案一：暴力遍历（时间复杂度O(n²)）

最直接的思路是对每个元素向后遍历数组，逐个查找更大的元素并记录下标。例如，对于元素arr[i]，从i+1开始遍历到数组末尾，依次记录遇到的比它大的元素下标，直到无更大元素为止。

代码片段：

def brute_force(arr):
    n = len(arr)
    result = [[] for _ in range(n)]
    for i in range(n):
        count = 0
        for j in range(i+1, n):
            if arr[j] > arr[i]:
                result[i].append(j)
    return result

缺点：
双重循环导致时间复杂度高达O(n²)，当数组长度较大时（如n=10⁵），效率极低，无法应对大规模数据。

方案二：单调栈（最优方案，时间复杂度O(n)）

利用单调递减栈可以大幅优化效率。栈中维护未找到后续更大元素的下标，遍历数组时，若当前元素大于栈顶元素，则栈顶元素找到第一个更大元素；继续弹出栈顶元素，可按顺序找到第二个、第三个更大元素（需结合辅助结构记录顺序）。

核心逻辑：

1. 遍历数组，若当前元素arr[i]大于栈顶元素arr[stack[-1]]，则弹出栈顶下标idx，将i加入result[idx]（第一个更大元素）。
2. 若栈仍不为空且arr[i]仍大于新栈顶元素，重复上述步骤，此时i成为前一个弹出元素的第二个更大元素，以此类推。
3. 最终栈中剩余元素无后续更大元素，结果记为-1或空列表。

代码片段：

def monotonic_stack(arr):
    n = len(arr)
    result = [[] for _ in range(n)]
    stack = []  # 存储下标，栈中元素对应的值单调递减
    for i in range(n):
        # 若当前元素大于栈顶元素，弹出并记录
        while stack and arr[i] > arr[stack[-1]]:
            idx = stack.pop()
            result[idx].append(i)  # 记录第1个、第2个...更大元素
        stack.append(i)  # 当前元素入栈
    # 处理栈中剩余元素（无后续更大元素）
    for idx in stack:
        result[idx] = [-1] if not result[idx] else result[idx]
    return result

优势：
每个元素最多入栈、出栈一次，时间复杂度O(n)，空间复杂度O(n)，是最优解法。以数组[4,5,2,7,3]为例，遍历到7时，会依次弹出2和5的下标，分别记录7为它们的第一个更大元素，效率显著高于暴力法。

方案三：单调栈+队列（记录顺序，时间复杂度O(n)）

若需要严格区分第k个更大元素（如第一个、第二个），可结合队列存储弹出顺序。每次弹出栈顶元素时，将其加入队列，当前元素i作为所有队列中元素的下一个更大元素（按弹出顺序确定第k个）。

代码片段：

from collections import deque

def stack_with_queue(arr):
    n = len(arr)
    result = [[] for _ in range(n)]
    stack = []
    for i in range(n):
        q = deque()
        while stack and arr[i] > arr[stack[-1]]:
            q.append(stack.pop())  # 暂存弹出元素
        # 按弹出顺序，当前i是q中元素的第1、2...个更大元素
        for idx in q:
            result[idx].append(i)
        stack.extend(q)  # 恢复栈顺序
        stack.append(i)
    return result

特点：
通过队列保证弹出顺序，明确第k个更大元素的顺序（如先弹出的元素先记录i为第一个更大元素，后弹出的记录为第二个），适用于需要严格区分k值的场景，时间复杂度仍为O(n)。

最优方案总结

单调栈（方案二）是最优解，其时间复杂度为O(n)，通过一次遍历和栈操作即可完成所有元素的查找。相比暴力法，效率提升显著，尤其适合大规模数据。代码实现简洁，核心在于利用栈维护递减序列，确保每个元素仅被处理一次。

希望以上分析对您有帮助，若有疑问可随时留言。请楼主采纳~