面试算法题：求解数组左侧最近较小元素的索引

嘿，我完全懂你面试时因为紧张卡壳的感觉——这种情况太常见了！咱们把这个问题拆解清楚，从理解到最优解法一步步来：

给定长度为n的整数数组Arr，构造长度相同的数组Sol：

• 对于每个下标i（0 ≤ i < n），Sol[i]是满足j < i且Arr[j] < Arr[i]的最大下标j；
• 如果没有符合条件的j，则Sol[i] = -1。

示例验证 #

你提到的输入示例：
Arr = [5,7,9,2,8,11,16,10,12]
对应的Sol数组是：[-1, 0, 1, -1, 3, 4, 5, 4, 7]
咱们逐个核对下关键项：

• i=3（Arr[3]=2）：左边所有元素都比2大，所以Sol[3] = -1
• i=4（Arr[4]=8）：左边比8小的元素下标有0、1、3，最大的是3，所以Sol[4] = 3
• i=7（Arr[7]=10）：左边元素里11、16都比10大，最近的比10小的是下标4对应的8，所以Sol[7] = 4

解法1：暴力枚举（易实现但效率有限） #

这是最容易想到的思路：对于每个i，从i-1开始往左遍历，找到第一个比Arr[i]小的元素的下标——因为是从右往左找，第一个符合条件的就是最大的j。

Python代码实现 #

def solve_bruteforce(arr):
    n = len(arr)
    sol = [-1] * n
    for i in range(1, n):
        # 从i-1向左遍历，找第一个比arr[i]小的元素下标
        for j in range(i-1, -1, -1):
            if arr[j] < arr[i]:
                sol[i] = j
                break
    return sol

# 测试示例
arr = [5,7,9,2,8,11,16,10,12]
print(solve_bruteforce(arr))  # 输出 [-1, 0, 1, -1, 3, 4, 5, 4, 7]

这个方法的时间复杂度是O(n²)，当数组长度很大（比如10^4以上）时会超时，所以面试中面试官通常会追问更高效的解法。

解法2：单调栈（最优解，O(n)时间复杂度） #

这是解决这类“找左侧/右侧第一个满足条件元素”问题的经典技巧，核心是维护一个单调递减栈，栈中存储的是数组下标，对应的数组元素值保持递减顺序。

核心思路 #

1. 初始化空栈和全为-1的Sol数组；
2. 遍历每个下标i：
   • 弹出栈中所有对应元素大于等于当前元素的下标（这些元素不可能成为后续元素的候选，因为当前元素更小且下标更大）；
   • 如果栈不为空，栈顶下标就是我们要找的最大j（因为栈是递减的，栈顶是左侧最近的、比当前元素小的最大下标）；
   • 将当前下标i压入栈，维持栈的单调递减性。

Python代码实现 #

def solve_monotonic_stack(arr):
    n = len(arr)
    sol = [-1] * n
    stack = []
    for i in range(n):
        # 弹出所有不满足arr[j] < arr[i]的栈顶元素
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        # 栈不为空时，栈顶就是目标下标
        if stack:
            sol[i] = stack[-1]
        # 当前下标入栈，维护单调递减性
        stack.append(i)
    return sol

# 测试示例
arr = [5,7,9,2,8,11,16,10,12]
print(solve_monotonic_stack(arr))  # 输出 [-1, 0, 1, -1, 3, 4, 5, 4, 7]

复杂度分析 #

• 时间复杂度：O(n)，每个元素最多入栈和出栈一次；
• 空间复杂度：O(n)，最坏情况下（比如数组严格递减）栈会存储所有下标。

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