数组查找Next Greater Element问题使用stack的核心逻辑是什么？

思路推导过程 #

第一步：先分析暴力解法的缺陷 #

暴力解法的逻辑很直观：对每个元素A[i]，从i+1的位置开始往后遍历，找到第一个比A[i]大的数就是ans[i]，找不到就填-1。这种方法的时间复杂度是O(n²)，最大的问题是存在大量重复比较：比如数组里的多个小数都要找同一个后面的大数，暴力解法会每个小数都单独遍历一遍路径，完全没有复用之前的比较结果。

第二步：思考优化方向 #

我们能不能在一次遍历的过程中，把「还没找到下一个更大元素」的数暂存起来，等遇到一个更大的新元素时，一次性给所有符合条件的暂存元素赋值？
这时候我们可以观察暂存元素的特性：如果我们从左到右遍历数组，能被暂存的元素一定是按值递减排列的。因为只要遇到比前一个元素大的数，前一个元素的下一个更大值就已经找到了，不需要再暂存。比如遍历[1,2,1,3]的时候：

• 第一个1暂时没找到更大的，暂存
• 遇到2，2比1大，1的结果就是2，1不需要再暂存，换成暂存2
• 遇到1，1比2小，找不到更大的，追加暂存，现在暂存列表是[2,1]（递减）
• 遇到3，3比暂存的最后一个元素1大，1的结果是3；继续看前一个暂存的2，3也比2大，2的结果是3；两个都不需要暂存了，换成暂存3

第三步：为什么用栈？ #

刚才的暂存操作有两个核心特征：

1. 新元素永远追加到暂存列表的末尾
2. 匹配的时候永远从暂存列表的末尾开始检查，符合条件就弹出赋值，直到遇到比当前元素大的就停止
   这完全符合栈「后进先出」的操作特性，而且我们维护的栈内元素永远保持单调递减，这就是单调栈解法的由来。

算法步骤 #

• 初始化一个空栈，用来存储还没找到下一个更大元素的下标（存下标是为了方便直接给ans数组对应位置赋值）
• 初始化ans数组，所有位置默认填-1
• 从左到右遍历数组A的每个下标i：
  • 只要栈不为空，且A[i] > A[栈顶元素]，就弹出栈顶元素top，设置ans[top] = A[i]
  • 把当前下标i压入栈
• 遍历结束后，ans数组就是最终结果

示例走读 #

拿你给出的示例A = [1,2,1,3,4]走一遍流程：

1. i=0，栈空，压入0，栈：[0]，ans：[-1,-1,-1,-1,-1]
2. i=1，A[1]=2 > A[0]=1，弹出0，ans[0]=2；栈空，压入1，栈：[1]，ans：[2,-1,-1,-1,-1]
3. i=2，A[2]=1 < A[1]=2，压入2，栈：[1,2]，ans：[2,-1,-1,-1,-1]
4. i=3，A[3]=3 > A[2]=1，弹出2，ans[2]=3；继续比较，A[3]=3 > A[1]=2，弹出1，ans[1]=3；栈空，压入3，栈：[3]，ans：[2,3,3,-1,-1]
5. i=4，A[4]=4 > A[3]=3，弹出3，ans[3]=4；栈空，压入4，栈：[4]，ans：[2,3,3,4,-1]
6. 遍历结束，栈里剩下的下标4对应的ans已经是-1，无需额外处理，最终结果和示例一致。

内容的提问来源于stack exchange，提问作者Kaneki