鉴于阵列发现在阵列的每个元素的下一个更小的元件，而不改变元素的原始顺序。

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

生成的阵列将是2,1，1,3，-1。

有人问我，在接受记者采访这个问题，但我也想不出解决办法不是小事为O（n ^ 2）解决方案更好。 我能想到的，也就是做一个二叉搜索树，或排序数组的任何做法，会扭曲要素的原有顺序，从而导致错误的结果。

任何帮助将是非常美联社preciated。

解决方案

O（N）算法

在初始化输出数组所有-1s。 的输出数组中创建，我们参观了输入数组中项目的索引空堆栈，但还不知道答案。 在迭代的输入数组中的每个元素： 是否小于由堆栈顶部索引的项小？ 是。这是第一个这样的元素是如此。在我们的输出数组中相应的元素填充，从堆栈中删除的项目，然后再试一次，直到堆栈为空或答案是否定的。 没有。继续3.2。 在加入该指数到堆栈中。从3继续迭代。

Python实现

 高清find_next_smaller_elements（XS）：
    YS =  -  1的X XS]
    堆栈= []
    对于I，X在历数（XS）：
        同时的len（堆栈）大于0且X; XS [堆叠[-1]]：
           YS [stack.pop（）] = X
        stack.append㈠
    返回伊苏

＆GT;＆GT;＆GT; find_next_smaller_elements（[4,2,1,5,3]）
[2，1，-1，3，-1]
＆GT;＆GT;＆GT; find_next_smaller_elements（[1,2,3,4,5]）
[-1，-1，-1，-1，-1]
＆GT;＆GT;＆GT; find_next_smaller_elements（[5,4,3,2,1]）
[4，3，2，1，-1]
＆GT;＆GT;＆GT; find_next_smaller_elements（[1,3,5,4,2]）
[-1，2，4，2，-1]
＆GT;＆GT;＆GT; find_next_smaller_elements（[6,4,2]）
[4,2，-1]
 

说明

工作原理

这工作，因为每当我们的项目添加到堆栈中，我们知道它的价值是在栈中大于或等于每一个元素了。当我们访问一个元素数组中，我们知道，如果它比的任意的堆栈中的项目，它必须比的最后的项目在堆栈低，因为较低最后一个项目一定是最大的。所以，我们不需要做任何的搜索在栈上，我们可以只考虑最后一个项目。

请注意：您可以跳过初始化步骤，只要你添加的最后一个步骤，以清空栈，并使用剩余的每个指标设置相应的输出数组元素为-1。它只是更容易在Python进行初始化，创建它时-1s。

时间复杂度

这是O（N）。主循环清楚地访问各指标一次。每个索引被添加到堆栈恰好一次除去至多一次。

解决作为一个面试问题

这样的问题可以pretty的恐吓在接受采访时，但我想指出的是，（希望）面试官是不会想到的解决方案，从你的头脑完全成形的春天。通过你的思维过程说服他们。矿去是这样的：

有数字的阵列中的位置和他们的下一个较小的数字之间有什么关系？是否知道他们中的一些限制哪些人有可能会是什么？ 如果我在白板我可能会勾画出例如数组，绘制各元素之间的前面。我也可能吸引他们为2D条形图 - 横轴是位置，输入数组和垂直轴是价值 在我有预感，这将显示出一个模式，但无纸的手。我认为该图将使其明显。仔细思考一下，我看得出来，行不会擅自重叠，但只会窝。 在围绕这一点，它发生，我认为这是非常相似的算法Python的内部使用转变缩进到INDENT和DEDENT语言虚拟代币，而我对前仔细阅读。请参阅编译器如何解析缩进？此页面上：http://www.secnetix.de/olli/Python/block_indentation.hawk然而，直到我实际工作了，我跟进了这一思想，并确定它实际上相同的算法，所以我不认为这帮助了太多。不过，如果你能看到一个相似你知道一些其他的问题，它可能是一个好主意，提到它，并说这是如何的相似，它是如何的不同。 从这里基于堆栈的算法一般形状变得明显，但我还是需要考虑一下多一点，以确保它的工作好于那些没有后续的更小的元素的元素。

即使你不拿出一个工作的算法，尽量让你的面试官看到你正在想什么。通常，它是思想的过程比他们感兴趣的答案了。对于一个棘手的问题，没有找到最好的解决办法，但表示洞察问题可能比知道一个罐头的回答更好，但不能够给它太多分析

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

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

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

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.

Any help would be highly appreciated.

解决方案

O(N) Algorithm

Initialize output array to all -1s. 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. Iterate over each element in the input array:

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

Yes. It is the first such element to be so. Fill in the corresponding element in our output array, remove the item from the stack, and try again until the stack is empty or the answer is no. No. Continue to 3.2.

Add this index to the stack. Continue iteration from 3.

Python implementation

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.

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.

Time complexity

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.

Solving as an interview question

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:

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.