数组中每个元素的下一个更小元素

1. 概述

在本篇文章中，我们将讨论一个经典数组问题：找出数组中每个元素的下一个更小元素（Next Smaller Element）。

我们会先明确问题定义，通过一个例子帮助理解。随后，我们介绍两种解决思路：
✅ 一种是直观但效率较低的暴力解法（O(n²)）
✅ 一种是使用栈结构优化的线性解法（O(n)）

2. 问题定义

给定一个整数数组 A，长度为 N。我们需要为每个元素 A[i] 找出其右侧第一个比它小的元素 A[j]，满足：

• j > i
• A[j] < A[i]
• j 尽可能小

如果找不到这样的元素，则返回 -1。

示例

数组为 [7, 3, 4, 1, 5, 3]，其每个元素的下一个更小元素如下：

• 7 → 3
• 3 → 1
• 4 → 1
• 1 → -1（没有更小）
• 5 → 3
• 3 → -1（没有更小）

3. 暴力解法（Naive Approach）

3.1 核心思想

对于每个元素，从它右边开始逐个比较，直到找到第一个比它小的元素。

3.2 实现代码（伪代码）

algorithm NaiveApproach(Arr):
    // INPUT
    //   Arr = an array of integers
    // OUTPUT
    //   Returns the next smaller element for each element in Arr

    next_smaller <- initialize an array of size N with -1
    for i <- 1 to N:
        for j <- i + 1 to N:
            if Arr[j] < Arr[i]:
                next_smaller[i] <- Arr[j]
                break

    return next_smaller

3.3 时间复杂度分析

• 时间复杂度：O(N²)
• 空间复杂度：O(N)

⚠️ 虽然实现简单，但在数据量较大时性能较差，容易超时。

4. 栈解法（Stack Approach）

4.1 核心思想

利用栈结构来维护“可能成为下一个更小元素”的候选值。

• 从右往左遍历数组
• 维护一个栈，栈顶元素始终是当前元素右侧第一个比它小的元素
• 如果栈顶比当前元素大或相等，则弹出，直到找到更小的或栈为空
• 最终栈顶即为当前元素的下一个更小元素

4.2 实现代码（伪代码）

algorithm StackApproach(Arr):
    // INPUT
    //   Arr = an array of integers
    // OUTPUT
    //   Returns the next smaller element for each element in Arr

    next_smaller <- initialize an array of size N with -1
    stack <- an empty stack
    for i <- N, N - 1, ..., 1:
        next_smaller[i] <- -1
        while not stack.empty() AND stack.top() >= Arr[i]:
            stack.pop()
        if not stack.empty():
            next_smaller[i] <- stack.top()
        stack.push(Arr[i])

    return next_smaller

4.3 时间复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

✅ 每个元素进栈一次、出栈最多一次，整体线性复杂度，效率远高于暴力解法。

5. 总结

我们讨论了如何为数组中每个元素找到右侧第一个更小的元素。

方法	时间复杂度	空间复杂度	适用场景
暴力解法	O(N²)	O(N)	数据量小
栈解法	O(N)	O(N)	数据量大推荐使用

✅ 推荐掌握栈解法，它是解决“下一个更大/更小”类问题的通用技巧，常用于面试和算法竞赛中。
⚠️ 踩坑提醒：遍历方向（从右到左）和栈的操作顺序容易写反，务必多做几遍手推练习。