给定一个数组,找出每个元素的下一个较小元素

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).主循环清楚地访问每个索引一次.每个索引都只添加到堆栈一次,最多删除一次.

解决面试问题

这种问题在面试中可能会非常令人生畏,但我想指出(希望)面试官不会期望解决方案从你的脑海中完全形成.通过思考过程与他们交谈.我的事情是这样的:

• 数字的位置与数组中下一个较小的数字之间是否存在某种关系？知道其中一些是否会限制其他人可能是什么？
• 如果我在白板前面,我可能会勾勒出示例数组并在元素之间绘制线条.我也可能将它们绘制为2D条形图 - 水平轴是输入数组中的位置,垂直轴是值.
• 我有预感,这会显示一种模式,但没有纸张可以用.我认为图表会显而易见.仔细思考,我可以看到线条不会任意重叠,但只能嵌套.
• 在这一点上,我突然意识到这与Python内部用于将缩进转换为INDENT和DEDENT虚拟标记的算法非常相似,我之前已经读过.请参阅"编译器如何解析缩进？" 在这个页面上:http://www.secnetix.de/olli/Python/block_indentation.hawk但是,直到我实际制定了一个算法,我才对这个想法采取了后续行动并确定它实际上是相同的所以我认为它没有太大帮助.尽管如此,如果你能看到与你知道的其他一些问题的相似之处,那么提一下这个问题可能是一个好主意,并说出它是如何相似的以及它是如何不同的.
• 从这里开始,基于堆栈的算法的一般形状变得明显,但我仍然需要考虑更多,以确保它对那些没有后续较小元素的元素可以正常工作.

即使你没有提出一个有效的算法,试着让你的面试官看到你在想什么.通常,思维过程不仅仅是他们感兴趣的答案.对于一个棘手的问题,未能找到最佳解决方案但是能够洞察问题可能比知道一个罐头答案更好但却无法给予它更多分析.