python算法例22 下一个更大的数

1. 问题描述

给定一个环形数组（最后一个元素的下一个元素是数组的第一个元素），为每个元素打印下一个更大的元素。数字x的下一个更大的数，是遍历数组的过程中出现的第一个更大的数字，这意味着可以循环搜索以查找其下一个更大的数字；如果它不存在，则为此数字输出-1。注意给定数组的长度不超过10000。

2. 问题示例

输入[1，2，1]，输出[2，-1，2]，第一个1的下一个更大的数字是2；数字2找不到下一个更大的数字；第二个1的下一个更大的数字需要循环搜索，答案也是2。

3. 代码实现

使用单调栈算法实现。单调栈算法是一种常用的栈操作技巧，它通过维护一个单调递减或单调递增的栈，来实现一些特定的操作。

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n  # 初始化结果列表为-1

    stack = []  # 使用一个栈来维护单调递减序列

    # 遍历两倍长度的数组，以处理循环的情况
    for i in range(2 * n):
        # 对于每个元素，不断弹出栈顶元素，直到栈顶元素小于当前元素或者栈为空
        while stack and nums[stack[-1]] < nums[i % n]:
            index = stack.pop()
            result[index] = nums[i % n]

        # 将当前元素的下标压入栈中
        stack.append(i % n)

    return result
nums = [1, 2, 1]
result = next_greater_element(nums)
print(result)

这个算法的时间复杂度是O(n)，其中n是数组的长度。

在算法中，我们遍历两倍长度的数组，并使用一个栈来维护单调递减序列。对于每个元素，我们不断弹出栈顶元素，直到栈顶元素小于当前元素或者栈为空，并将当前元素的下标压入栈中。最后，我们得到每个元素的下一个更大的元素。因此，整个算法的时间复杂度是O(n)。