arrays - 给定一个数组，找出每个元素的下一个较小的元素

Question

给定一个数组，在不改变元素原始顺序的情况下，为每个元素找到数组中下一个较小的元素。

例如，假设给定的数组是 4,2,1,5,3。

结果数组为 2,1,-1,3,-1。

我在一次采访中被问到这个问题，但我想不出比简单的 O(n^2) 解决方案更好的解决方案。 我能想到的任何方法，即制作二叉搜索树或对数组进行排序，都会扭曲元素的原始顺序，从而导致错误的结果。

如有任何帮助，我们将不胜感激。

Answer 1

O(N)算法

1. 将输出数组初始化为所有 -1。
2. 为我们在输入数组中访问过但在输出数组中还不知道答案的项目创建一个空的索引堆栈。
3. 遍历输入数组中的每个元素:
   1. 它是否小于堆栈顶部索引的项目？
      1. 是的。这是第一个这样的元素。在我们的输出数组中填充相应的元素，从堆栈中移除该项目，然后重试，直到堆栈为空或答案是否定的。
      2. 没有。继续 3.2。
   2. 将这个索引添加到堆栈中。从 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)。主循环显然访问每个索引一次。每个索引只添加到堆栈一次，最多删除一次。

作为面试题解决

这类问题在面试中可能会让人望而生畏，但我想指出(希望如此)面试官不会期望解决方案会从您的脑海中浮现出来。通过您的思考过程与他们交谈。我的是这样的:

• 数组中数字的位置与其下一个较小的数字之间是否存在某种关系？了解其中一些是否会限制其他可能的内容？
• 如果我在白板前，我可能会画出示例数组并在元素之间画线。我也可以将它们绘制为二维条形图 - 水平轴是输入数组中的位置，垂直轴是值。
• 我有预感这会显示出一种模式，但手边没有纸。我认为该图会使它显而易见。仔细想想，线条不会随意重叠，只会嵌套。
• 围绕这一点，我突然想到，这与 Python 在内部使用的将缩进转换为 INDENT 和 DEDENT 虚拟标记的算法非常相似，我之前读过这种算法。请参阅“编译器如何解析缩进？”在这个页面上:http://www.secnetix.de/olli/Python/block_indentation.hawk然而，直到我真正研究出一个算法，我才跟进这个想法并确定它实际上是一样的，所以我认为它没有太大帮助。尽管如此，如果您发现与您知道的其他问题有相似之处，不妨提及它，并说明它的相似之处和不同之处。
• 从这里开始，基于堆栈的算法的一般形状变得明显，但我仍然需要多考虑一下，以确保它适用于那些没有后续较小元素的元素。

即使您没有提出可行的算法，也请尝试让面试官了解您的想法。通常他们感兴趣的是思考过程而不是答案。对于一个棘手的问题，未能找到最佳解决方案但表现出对问题的洞察力可能比知道固定答案但不能给出太多更好分析。