O（N）算法

1. 将输出数组初始化为所有-1。
2. 创建一个空的索引堆栈，这些索引是我们在输入数组中访问过的项目的索引，但尚不知道输出数组中的答案。
3. 遍历输入数组中的每个元素：
   1. 它小于堆栈顶部索引的项目吗？
   2. 是。这是第一个这样的元素。填写输出数组中的相应元素，从堆栈中删除该项目，然后重试直到堆栈为空或答案为否。
   3. 否。继续3.2。
   4. 将此索引添加到堆栈中。从3继续迭代。

Python实现

def find_next_smaller_elements(xs):
    ys=[-1 for x in xs]
    stack=[]
    for i,x in enumerate(xs):
        while len(stack)>0 and x<xs[stack[-1]]:
           ys[stack.pop()]=x
        stack.append(i)
    return ys

>>> find_next_smaller_elements([4,2,1,5,3])
[2, 1, -1, 3, -1]
>>> find_next_smaller_elements([1,2,3,4,5])
[-1, -1, -1, -1, -1]
>>> find_next_smaller_elements([5,4,3,2,1])
[4, 3, 2, 1, -1]
>>> find_next_smaller_elements([1,3,5,4,2])
[-1, 2, 4, 2, -1]
>>> find_next_smaller_elements([6,4,2])
[4, 2, -1]

说明

这个怎么运作

之所以可行，是因为每当我们将一个项目添加到堆栈中时，我们就知道它的值已经大于或等于堆栈中的每个元素。当我们访问数组中的一个元素时，我们知道如果它比堆栈中的
任何 项目都低，则它必须比堆栈中的 最后一个 项目低，因为最后一个项目必须最大。因此，我们无需在堆栈上进行任何类型的搜索，只需考虑最后一项即可。

注意：只要添加最后一步以清空堆栈，并使用每个剩余的索引将相应的输出数组元素设置为-1，就可以跳过初始化步骤。在Python中创建时将其初始化为-1s更加容易。

时间复杂度

这是O（N）。主循环清楚地访问每个索引一次。每个索引仅一次添加到堆栈中，一次最多删除一次。

解决为面试问题

这种问题在面试中可能会令人生畏，但我想指出，（希望）面试官不会期望解决方案能从您的头脑中完全形成。在您的思考过程中与他们交谈。我的事情是这样的：

• 数字的位置与数组中的下一个较小数字之间是否存在某种关系？知道其中一些会约束其他人可能是什么吗？
• 如果我在白板前，我可能会勾勒出示例数组并在元素之间画线。我也可以将它们绘制为2D条形图-水平轴是输入数组中的位置，垂直轴是值。
• 我预感这会显示出一种模式，但是没有纸可拿。我认为该图将使其显而易见。仔细考虑一下，我可以看到线条不会任意重叠，而只会嵌套。
• 在这一点上，我发现这非常类似于Python内部使用的将缩进转换为INDENT和DEDENT虚拟令牌的算法，这在我之前已经读过。请参阅“编译器如何解析缩进？” 在此页面上：http : //www.secnetix.de/olli/Python/block_indentation.hawk但是，直到我实际制定出一种算法后，我才根据这种思想确定实际上是相同的。 ，因此我认为它没有太大帮助。但是，如果您可以看到与您知道的其他问题的相似性，则最好提起它，并说出它的相似之处和不同之处。
• 从这里开始，基于堆栈的算法的总体形状就显而易见了，但是我仍然需要多考虑一下，以确保对于没有后续较小元素的那些元素来说，它可以正常工作。

即使您没有提出有效的算法，也要尝试让面试官了解您的想法。通常，思考过程比他们感兴趣的答案要多。对于一个棘手的问题，如果找不到最佳的解决方案但对问题有深刻的了解，可能比知道罐头的答案但不能给予太多帮助更好。分析。