如何用栈实现O(n)时间复杂度的相邻较小元素计数？

嘿，别头疼啦！这个问题完全不用递归，用单调栈就能搞定，而且时间复杂度刚好是O(n)。我给你拆解清楚思路，再附上Python的实现代码，保证一看就懂～

核心思路：单调递减栈 #

我们需要维护一个单调递减栈（栈里的元素从栈底到栈顶是递减的），栈里的每个元素存储两个信息：(元素值, 该元素左侧比它小的元素数量)。

遍历数组时，对每个元素num：

• 初始化计数count为0
• 不断弹出栈中值小于当前num的元素：每弹出一个元素，就把它的计数+1加到count里（因为这个元素本身比num小，再加上它左侧比它小的所有元素，总共计数+1个元素都比num小）
• 如果栈里还有值等于num的元素，也弹出并把它的计数加到count里（等于的元素不算比num小，但它左侧的小元素都算）
• 当栈顶元素值大于num时，停止弹出
• 把当前count加入结果列表，再把(num, count)压入栈中

这样每个元素只会入栈、出栈一次，时间复杂度自然是O(n)。

Python 实现代码 #

def count_smaller_left(arr):
    stack = []
    result = []
    for num in arr:
        count = 0
        # 弹出所有比当前元素小的栈元素，累加计数
        while stack and stack[-1][0] < num:
            count += stack.pop()[1] + 1
        # 处理等于当前元素的情况，累加其左侧小元素的计数
        while stack and stack[-1][0] == num:
            count += stack.pop()[1]
        # 栈顶元素大于当前元素，停止弹出
        result.append(count)
        stack.append((num, count))
    return result

# 测试示例输入
input_arr = [100, 80, 60, 70, 60, 75, 85]
print(count_smaller_left(input_arr))  # 输出: [0, 0, 0, 1, 0, 3, 5]

示例流程验证 #

咱们对应示例走一遍流程，就能彻底明白栈的作用：

1. 处理100：栈为空，计数0，直接入栈 → 结果：[0]
2. 处理80：栈顶100比它大，计数0，入栈 → 结果：[0, 0]
3. 处理60：栈顶80比它大，计数0，入栈 → 结果：[0, 0, 0]
4. 处理70：弹出60（计数0+1=1），栈顶80比70大，停止，计数1入栈 → 结果：[0, 0, 0, 1]
5. 处理60：栈顶70比它大，计数0，入栈 → 结果：[0, 0, 0, 1, 0]
6. 处理75：弹出60（0+1=1）、弹出70（1+1=2，累计3），栈顶80比75大，停止，计数3入栈 → 结果：[0, 0, 0, 1, 0, 3]
7. 处理85：弹出75（3+1=4）、弹出80（0+1=1，累计5），栈顶100比85大，停止，计数5入栈 → 结果：[0, 0, 0, 1, 0, 3, 5]

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