如何在Python中从峰谷序列列表里查找下一个更小的数

给定数组：Array = [3, 6, 5, 7, 2, 4, 3, 5, 4, 5, 4, 7, 6, 7, 1, 7, 4, 6, 3]，需求为数组中每个元素找到其右侧第一个比它小的元素；若不存在这样的元素，用-1标记。

示例参考 #

数值序列：3, 6, 5, 7, 2, 4, 3, 5, 4, 5, 4, 7, 6, 7, 1, 7, 4, 6, 3
谷(valley)/峰(Peak)：v, p, v, p, v, p, v, p, v, p, v, p, v, p, v, p, v, p, v

高效实现方案（单调栈） #

暴力遍历的时间复杂度为O(n²)，而使用单调栈可以将时间复杂度优化至O(n)，具体实现代码如下：

def find_next_smaller(arr):
    n = len(arr)
    result = [-1] * n
    stack = []
    
    # 从右往左遍历数组
    for i in range(n-1, -1, -1):
        # 弹出栈中所有不小于当前元素的元素，这些元素无法成为当前元素的下一个更小值
        while stack and stack[-1] >= arr[i]:
            stack.pop()
        # 栈不为空时，栈顶即为第一个更小的元素
        if stack:
            result[i] = stack[-1]
        # 将当前元素压入栈，作为左侧元素的候选值
        stack.append(arr[i])
    return result

# 测试给定数组
target_array = [3, 6, 5, 7, 2, 4, 3, 5, 4, 5, 4, 7, 6, 7, 1, 7, 4, 6, 3]
next_smaller_values = find_next_smaller(target_array)

print("原数组:", target_array)
print("下一个更小值序列:", next_smaller_values)

代码说明 #

• 初始化result数组，默认值设为-1，代表无符合条件的元素。
• 从右往左遍历数组，利用栈维护一个单调递增序列：栈中始终保存当前元素右侧可能成为“下一个更小值”的候选元素。
• 对每个元素，先清除栈中所有大于等于它的元素（这些元素不可能是当前元素的目标值），此时栈顶元素即为第一个更小值；若栈为空则保持-1。
• 将当前元素压入栈，为左侧元素提供候选。

运行结果 #

原数组: [3, 6, 5, 7, 2, 4, 3, 5, 4, 5, 4, 7, 6, 7, 1, 7, 4, 6, 3]
下一个更小值序列: [2, 5, 2, 2, -1, 3, 1, 4, 1, 4, 1, 6, 1, 1, -1, 4, 3, 3, -1]

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