给定一个数组，找出每个元素的下一个较小的元素 [英] Given an array, find out the next smaller element for each element

问题描述

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

Given an array find the next smaller element in array for each element without changing the original order of the elements.

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

For example, suppose the given array is 4,2,1,5,3.

结果数组将为 2,1,-1,3,-1.

The resultant array would be 2,1,-1,3,-1.

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

I was asked this question in an interview, but i couldn't think of a solution better than the trivial O(n^2) solution. Any approach that I could think of, i.e. making a binary search tree, or sorting the array, will distort the original order of the elements and hence lead to a wrong result.

任何帮助将不胜感激.

推荐答案

O(N) 算法

1. 将输出数组初始化为所有 -1.
2. 为我们在输入数组中访问过但还不知道输出数组中的项目的索引创建一个空栈.
3. 迭代输入数组中的每个元素:

1. Initialize output array to all -1s.
2. Create an empty stack of indexes of items we have visited in the input array but don't yet know the answer for in the output array.
3. Iterate over each element in the input array:

1. 它是否比栈顶索引的项目小?

1. Is it smaller than the item indexed by the top of the stack?

1. 是的.这是第一个这样的元素.在我们的输出数组中填充相应的元素，从堆栈中删除该项目，然后再试一次，直到堆栈为空或答案是否定的.
2. 没有.继续 3.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]

说明

工作原理

这是有效的，因为每当我们向堆栈中添加一个项目时，我们知道它的值大于或等于堆栈中的每个元素.当我们访问数组中的一个元素时，我们知道如果它低于堆栈中的任何项，则它必须低于堆栈中的最后项，因为最后一项必须是最大的.所以我们不需要在堆栈上做任何类型的搜索，我们可以只考虑最后一项.

Explanation

How it works

This works because whenever we add an item to the stack, we know its value is greater or equal to every element in the stack already. When we visit an element in the array, we know that if it's lower than any item in the stack, it must be lower than the last item in the stack, because the last item must be the largest. So we don't need to do any kind of search on the stack, we can just consider the last item.

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

Note: You can skip the initialization step so long as you add a final step to empty the stack and use each remaining index to set the corresponding output array element to -1. It's just easier in Python to initialize it to -1s when creating it.

这是 O(N).主循环清楚地访问每个索引一次.每个索引只添加到堆栈一次，最多删除一次.

This is O(N). The main loop clearly visits each index once. Each index is added to the stack exactly once and removed at most once.

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

This kind of question can be pretty intimidating in an interview, but I'd like to point out that (hopefully) an interviewer isn't going to expect the solution to spring from your mind fully-formed. Talk them through your thought process. Mine went something like this:

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

• Is there some relationship between the positions of numbers and their next smaller number in the array? Does knowing some of them constrain what the others might possibly be?
• If I were in front of a whiteboard I would probably sketch out the example array and draw lines between the elements. I might also draw them as a 2D bar graph - horizontal axis being position in input array and vertical axis being value.
• I had a hunch this would show a pattern, but no paper to hand. I think the diagram would make it obvious. Thinking about it carefully, I could see that the lines would not overlap arbitrarily, but would only nest.
• Around this point, it occurred to me that this is incredibly similar to the algorithm Python uses internally to transform indentation into INDENT and DEDENT virtual tokens, which I'd read about before. See "How does the compiler parse the indentation?" on this page: http://www.secnetix.de/olli/Python/block_indentation.hawk However, it wasn't until I actually worked out an algorithm that I followed up on this thought and determined that it was in fact the same, so I don't think it helped too much. Still, if you can see a similarity to some other problem you know, it's probably a good idea to mention it, and say how it's similar and how it's different.
• From here the general shape of the stack-based algorithm became apparent, but I still needed to think about it a bit more to be sure it would work okay for those elements that have no subsequent smaller element.

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

Even if you don't come up with a working algorithm, try to let your interviewer see what you're thinking about. Often it is the thought process more than the answer that they're interested in. For a tough problem, failing to find the best solution but showing insight into the problem can be better than knowing a canned answer but not being able to give it much analysis.

这篇关于给定一个数组，找出每个元素的下一个较小的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！