如何找出数组中每个元素右侧的下一个更小值？

嘿，太懂你这种卡在O(n²)解法里，明明感觉有更优解却摸不到门道的痛苦了！其实你之前想到的栈就是正确方向——这题的标准最优解法就是单调栈，刚好能做到O(n)的时间复杂度，每个元素入栈、出栈各一次，完全没有冗余操作。

我给你拆解清楚怎么用，再结合你给的例子一步步走，保证你能搞明白：

我们从数组的尾部开始倒着遍历，维护一个「单调递增」的栈——栈里的元素是我们已经处理过的右侧元素，栈顶永远是当前元素右侧最近的更小值候选。每次处理当前元素时：

1. 先把栈里所有大于等于当前元素的元素弹出，因为它们不可能成为当前元素（或者更左侧元素）的下一个更小值了；
2. 如果栈不为空，栈顶就是当前元素的下一个更小值；如果栈空了，说明当前元素右侧没有更小值；
3. 最后把当前元素压入栈，作为更左侧元素的候选。

用你的例子一步步走 #

数组：[4, 5, 2, 6, 7, 1]，初始化结果数组全为-1（代表无更小值），栈为空。

• 处理1：栈空，结果[5] = -1，把1入栈 → 栈：[1]
• 处理7：栈顶1 < 7，结果[4] = 1，把7入栈 → 栈：[1,7]
• 处理6：栈顶7 ≥6，弹出7；现在栈顶1 <6，结果[3] =1，把6入栈 → 栈：[1,6]
• 处理2：栈顶6 ≥2，弹出6；栈顶1 <2，结果[2] =1，把2入栈 → 栈：[1,2]
• 处理5：栈顶2 <5，结果[1] =2，把5入栈 → 栈：[1,2,5]
• 处理4：栈顶5 ≥4，弹出5；栈顶2 <4，结果[0] =2，把4入栈 → 栈：[1,2,4]

最终结果数组就是[2,2,1,1,1,-1]，完全符合你描述的需求！

直接返回下一个更小值的版本 #

def next_smaller_element(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

# 测试你的例子
arr = [4,5,2,6,7,1]
print(next_smaller_element(arr))  # 输出: [2, 2, 1, 1, 1, -1]

如果需要返回更小值的索引（而不是值） #

有时候我们需要知道更小值的位置，只需要把栈里存索引就行：

def next_smaller_element_indices(arr):
    n = len(arr)
    result = [-1] * n
    stack = []
    
    for i in range(n-1, -1, -1):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        if stack:
            result[i] = stack[-1]
        stack.append(i)
    
    return result

arr = [4,5,2,6,7,1]
print(next_smaller_element_indices(arr))  # 输出: [2, 2, 5, 5, 5, -1]

其实也可以从数组头部开始遍历，维护单调递增栈，此时栈里存的是还没找到下一个更小值的元素索引。当遇到一个更小的元素时，就为栈里所有比它大的元素设置结果：

def next_smaller_element_forward(arr):
    n = len(arr)
    result = [-1] * n
    stack = []
    
    for i in range(n):
        # 当前元素是栈顶元素的下一个更小值
        while stack and arr[i] < arr[stack[-1]]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)
    
    return result

arr = [4,5,2,6,7,1]
print(next_smaller_element_forward(arr))  # 输出: [2, 2, 1, 1, 1, -1]

每个元素最多被压入栈一次，弹出一次，总操作次数是2n，所以时间复杂度是严格的O(n)，完全没有嵌套循环的额外开销。你之前可能是没处理好栈的弹出逻辑，导致栈里留了无效的候选，才会顾此失彼～

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