使用堆栈在数组中查找下一个更大的元素背后的真正直觉是什么
What is the real intuition behind using stack in finding Next Greater Element in Array
我在面试中被问到一个问题，该问题返回 ans 数组，其中 ans[i] = next greater element of A[i] 如果元素没有下一个更大的，则将 -1 放在那里。
Example:
A = [1, 2, 1, 3, 4]
ans = [2, 3, 3, 4, -1]
我无法给出优化的方法，但我在互联网上搜索并发现我们可以使用堆栈来完成它，但在任何地方我都只是找到解决问题的算法而不是 reason/intuition 这就是为什么有效，在阅读之后我也同意是的，它会很好地工作但是从未做过这个问题的人会如何考虑使用堆栈。
如果有人能帮助我，那将是一个很大的帮助！ :)
您可以将输入想象成代表垂直条形图中的条形。例如：
箭头表示较高的条形对其左侧具有的某种“影响”。您可以想象有人站在酒吧的顶部并向左看。或者你可以想象那些条形之间充满的水，当它达到当前条形的高度时，你就知道它们的影响范围。他们的影响在遇到至少有自己高度的条形或遇到图表左侧时停止。
较高的条通常具有较长的影响力，这是有道理的。
现在当我们从左到右迭代条形图时，我们可以看到如何使用它来生成输出。 7 对 2 有影响，因此将 7 添加到索引 0（值 2 的索引）处的输出。
下一个感兴趣的值是 4。它影响前面两个值，因此在它们的索引处（即索引 3 和 4）我们应该输出 4。
下一个感兴趣的值是 6。它对更多值有影响，其中只有索引 2 处的 5 是“新”。所以在索引 2 处我们应该输出 6.
我们注意到对于索引 1 的输出（覆盖值 7），我们需要继续该过程直到达到值 8。同时可以确定一些输出，而 7 应该“等待”找到下一个更大的价值。
这应该会给您一种使用堆栈的感觉。对索引 4、3、2、1 的赋值是按倒序进行的，就像从堆栈中弹出这些索引时得到的那样。在索引 1 被弹出之前，一些索引将被推入堆栈并再次弹出，但最后 7 也可以被弹出，结束其较长的等待。
此弹出还确保输出索引只会被分配一个值一次。
我知道你不需要看算法本身，因为你已经知道了。希望这有助于澄清其背后的直觉。
在 A 的递增部分中，下一个更大的元素就是下一个。而当出现下降时，你必须等待，直到达到更大的值。
例如
1, 2, 1, 3, 4
可以看成两个递增的段
1, 2||1, 3, 4
给出下一个更大的元素
2, -||3, 4, -
当你到达2（在原数组中），你必须等到3（在原数组中）并得出结论
2, 3, 3, 4, -
当您到达 4（在原始数组中）时，您必须等待...永远等待，因为没有更大的元素。
现在需要堆栈是因为如果您从左到右前进，可能会有多个等待元素。由于这些元素形成一个递减的部分，它们将首先“服务”最小的，这对应于后进先出顺序。
我在面试中被问到一个问题，该问题返回 ans 数组，其中 ans[i] = next greater element of A[i] 如果元素没有下一个更大的，则将 -1 放在那里。
Example:
A = [1, 2, 1, 3, 4]
ans = [2, 3, 3, 4, -1]
我无法给出优化的方法，但我在互联网上搜索并发现我们可以使用堆栈来完成它，但在任何地方我都只是找到解决问题的算法而不是 reason/intuition 这就是为什么有效，在阅读之后我也同意是的，它会很好地工作但是从未做过这个问题的人会如何考虑使用堆栈。
如果有人能帮助我，那将是一个很大的帮助！ :)
您可以将输入想象成代表垂直条形图中的条形。例如：
箭头表示较高的条形对其左侧具有的某种“影响”。您可以想象有人站在酒吧的顶部并向左看。或者你可以想象那些条形之间充满的水，当它达到当前条形的高度时，你就知道它们的影响范围。他们的影响在遇到至少有自己高度的条形或遇到图表左侧时停止。
较高的条通常具有较长的影响力，这是有道理的。
现在当我们从左到右迭代条形图时，我们可以看到如何使用它来生成输出。 7 对 2 有影响，因此将 7 添加到索引 0（值 2 的索引）处的输出。
下一个感兴趣的值是 4。它影响前面两个值，因此在它们的索引处（即索引 3 和 4）我们应该输出 4。
下一个感兴趣的值是 6。它对更多值有影响，其中只有索引 2 处的 5 是“新”。所以在索引 2 处我们应该输出 6.
我们注意到对于索引 1 的输出（覆盖值 7），我们需要继续该过程直到达到值 8。同时可以确定一些输出，而 7 应该“等待”找到下一个更大的价值。
这应该会给您一种使用堆栈的感觉。对索引 4、3、2、1 的赋值是按倒序进行的，就像从堆栈中弹出这些索引时得到的那样。在索引 1 被弹出之前，一些索引将被推入堆栈并再次弹出，但最后 7 也可以被弹出，结束其较长的等待。
此弹出还确保输出索引只会被分配一个值一次。
我知道你不需要看算法本身，因为你已经知道了。希望这有助于澄清其背后的直觉。
在 A 的递增部分中，下一个更大的元素就是下一个。而当出现下降时，你必须等待，直到达到更大的值。
例如
1, 2, 1, 3, 4
可以看成两个递增的段
1, 2||1, 3, 4
给出下一个更大的元素
2, -||3, 4, -
当你到达2（在原数组中），你必须等到3（在原数组中）并得出结论
2, 3, 3, 4, -
当您到达 4（在原始数组中）时，您必须等待...永远等待，因为没有更大的元素。
现在需要堆栈是因为如果您从左到右前进，可能会有多个等待元素。由于这些元素形成一个递减的部分，它们将首先“服务”最小的，这对应于后进先出顺序。