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

问题描述

给定的阵列中找到阵列的每个元素的下一个更小的元素，而不改变元素的原始顺序。

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

得到的阵列将是2,1，1,3，-1。

有人问我在采访这个问题，但我想不出比平凡为O（n ^ 2）解决方案，更好的解决方案。
我能想到的，即制作二叉搜索树，或排序数组的任何做法，会扭曲元素的原始顺序，从而导致错误的结果。

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

解决方案

O（N）算法

1. 初始化输出数组所有-1s。


2. 的输出数组中创建我们输入数组中访问项目的索引空堆栈，但还不知道答案。


3. 迭代输入数组中的每个元素：
   
   
   
   1. 它是不是由堆栈顶部索引的项小？
      
      
      
      1. 是。它是如此的第一个这样的元件。填写我们输出数组的相应元素，从堆栈中删除的项目，然后重新尝试，直到堆栈为空或答案是否定的。
      
      
      2. 没有。继续3.2。
      
      
   
   
   2. 添加这个索引到堆栈中。从3继续迭代。
   
   

Python实现

 高清find_next_smaller_elements（XS）：
    YS = [ -  1为XS X]
    堆栈= []
    对于我，在历数（XS）X：
        而LEN（堆栈）大于0和X; XS [堆叠[-1]：
           YS [stack.pop（）] = X
        stack.append㈠
    返回YS＆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内部使用转换成缩进缩进和DEDENT语言虚拟代币，这我约前仔细阅读。请参阅编译器如何解析缩进？此页面上：<一href=\"http://www.secnetix.de/olli/Python/block_indentation.hawk\">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

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. Is it smaller than the item indexed by the top of the stack?
      1. 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.
      2. No. Continue to 3.2.

   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.

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