1019. 链表中的下一个更大节点

妖狐艹你老母 2023-02-22 08:22 69阅读 0赞

# 题目来源 #

[1019. 链表中的下一个更大节点][1019.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

这题考单调栈

而所谓 单调栈 则是在栈的 先进后出 基础之上额外添加一个特性：从栈顶到栈底的元素是严格递增（or递减）。

具体进栈过程如下：

*  对于单调递增栈，若当前进栈元素为 e，从栈顶开始遍历元素，把小于 e 或者等于 e 的元素弹出栈，直接遇到一个大于 e 的元素或者栈为空为止，然后再把 e 压入栈中。
 *  对于单调递减栈，则每次弹出的是大于 e 或者等于 e 的元素

例子  
以 单调递增栈 为例进行说明。

现在有一组数

3，4，2，6，4，5，2，3  
让它们从左到右依次入栈。

具体过程如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][20200702165929474.gif]

public static int[] nextLargerNodes(ListNode head) {
        
    
            ArrayList<Integer> list = new ArrayList<>();
            while (head != null){
        
                list.add(head.val);
                head = head.next;
            }
    
            int [] res = new int[list.size()];
    
            // 栈压入两个东西： 当前值的索引 | 当前值 | 当前值的索引 | 当前值
            Stack<Integer> stack = new Stack<>();
    
            for (int i = 0; i < list.size(); i++){
        
                int cur = list.get(i);
                while (!stack.empty() && cur > stack.peek() ){
          // 需要淘汰比他小的
                    stack.pop();
                    res[stack.pop()] = cur;
                }
                stack.push(i);
                stack.push(cur);
            }
    
            return res;
        }

![在这里插入图片描述][20200702170032784.png]

[1019.]: https://leetcode-cn.com/problems/next-greater-node-in-linked-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200702170107559.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200702165322132.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200702165929474.gif]: https://img-blog.csdnimg.cn/20200702165929474.gif
[20200702170032784.png]: https://img-blog.csdnimg.cn/20200702170032784.png