使用堆栈查找数组中的下一个更大元素背后的真正直觉是什么 [英] What is the real intuition behind using stack in finding Next Greater Element in Array

问题描述

我在面试中被问到一个问题，它返回 ans 数组，其中 ans[i] = A[i] 的下一个更大的元素，如果元素没有下一个更大的 put-1 在那里.

I was asked of a question in my interview which was returning ans array in which, ans[i] = next greater element of A[i] and if element don't have next greater put -1 there.

Example: 
A = [1, 2, 1, 3, 4]
ans = [2, 3, 3, 4, -1]   

我无法给出优化的方法，但是我在互联网上搜索并发现我们会使用堆栈来完成它，但是在阅读之后，我到处都找到了解决问题的算法，而不是为什么这样做的原因/直觉我也同意是的，这会工作得很好，但是从未做过这个问题的人会如何考虑使用堆栈.

I was not able to give optimized approach, but I searched on internet and found it will we done using a stack, but everywhere I just found the algo of solving the question not the reason/intuition that why this works, after reading also I also agree yes that will work fine but how will someone who never did this question will think towards of using a stack.

如果有人可以帮助我，那将是一个很大的帮助！:)

If anyone could help me out it will be a great help! :)

推荐答案

您可以将输入想象成表示垂直条形图中的条形.例如:

You could imagine the input as representing bars in a vertical bar chart. For example:

箭头表示一种影响"；更高的酒吧必须在他们的左侧.你可以想象有人站在吧台的顶部向左看.或者，您可以想象在这些条形之间充满水，当它达到当前条形的高度时，您就知道它们的影响范围.它们的影响在遇到至少具有它们自身高度的条形时停止，或者在遇到图表左侧时停止.

The arrows indicate a sort of "influence" that higher bars have to their left side. You could imagine someone standing at the top of the bar and looking towards the left. Or you could think of water that fills up between those bars, and when it reaches the height of the current bar, you know their field of influence. Their influence stops where a bar is encountered that has at least their own height, or when the left side of the chart is encountered.

较高的条形通常具有较长的影响范围，这是有道理的.

It makes sense that higher bars typically have a longer stretch of influence.

现在，当我们从左到右迭代条形时，我们可以看到如何使用它来生成输出.7 对 2 有影响，因此将 7 添加到索引 0(值 2 的索引)处的输出中.

Now when we iterate the bars from left to right we can see how this can be used to produce the output. The 7 has influence over the 2, so 7 is added to the output at index 0 (the index of value 2).

下一个感兴趣的值是 4.它会影响前面的两个值，因此在它们的索引处(即索引 3 和 4)，我们应该输出 4.

The next value of interest, is 4. It has influence over two preceding values, so at their indices (i.e. at index 3 and 4) we should output 4.

下一个感兴趣的值是 6.它对更多值有影响，其中只有索引 2 处的 5 是新的".所以在索引 2 处我们应该输出 6.

The next value of interest, is 6. It has influence over more values, of which only the 5 at index 2 is "new". So at index 2 we should output 6.

我们注意到，对于索引 1 处的输出(覆盖值 7)，我们需要继续该过程直到达到值 8.一些输出可以同时确定，而 7 应该等待".寻找下一个更大的价值.

We note that for an output at index 1 (to cover for value 7) we need to continue the process until reaching value 8. Some outputs can be determined in the mean time, while the 7 should "wait" for its next greater value to be found.

这应该让您有一种使用堆栈的感觉.对索引 4, 3, 2, 1 的赋值是按倒序进行的，就像从堆栈中弹出这些索引时得到的一样.在索引 1 被弹出之前，一些索引会被压入堆栈并再次弹出，但最后 7 也可以被弹出，结束其较长的等待.

This should give you a feel of using a stack. The assignment to index 4, 3, 2, 1 happened in backwards order, much like you get when popping those indices from a stack. Before index 1 would be popped, some indices would be pushed to the stack and popped again, but finally 7 can be popped too, ending its longer wait.

这种弹出还确保输出索引只会被分配一次.

This popping also ensures that an output index will only be assigned a value once.

我意识到您不需要查看算法本身，因为您已经知道了.希望这有助于澄清其背后的直觉.

I realise you don't need to see the algorithm itself, as you already know it. Hopefully this helped clarify a bit what the intuition is behind it.

这篇关于使用堆栈查找数组中的下一个更大元素背后的真正直觉是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！