LeetCode链表算法——1019. 链表中的下一个更大节点

朴灿烈づ我的快乐病毒、 2021-10-18 11:22 131阅读 0赞

题目描述：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWppdWppdTMz_size_16_color_FFFFFF_t_70]  
题目链接：[链表中的下一个更大节点][Link 1]

读懂题目大致意思就是：求出链表每个结点的“最大值”，该“最大值”指的是，其后第一个结点值比他大的结点的值  
首先我想到的就是：两次循环，遍历每个结点，每个结点再往后遍历，找出其后第一个最大的结点的值即可  
详细代码：

public int[] nextLargerNodes(ListNode head) { 
    
            if (head == null) { 
                return new int[0];
            }
    
            ListNode frist = head;
            ListNode front = head;
    
            // 先获取链表的长度
            int length = 1;
            while (head.next != null) { 
                length++;
                head = head.next;
            }
    
            int[] ints = new int[length];
    
            // 两次循环，时间复杂度（n*n）过高，超过时间限制，不推荐
            for (int i = 0; i < length - 1; i++) { 
                for (int j = i; j < length - 1; j++) { 
                    if (front.next != null && front.next.val > frist.val) { 
                        ints[i] = front.next.val;
                        break;
                    }
                    front = front.next;
                }
                frist = frist.next;
                front = frist;
            }
            return ints;
        }

感觉很简单，但是很遗憾，提交的时候，LeetCode显示超出时间限制，不予通过  
![在这里插入图片描述][20190811190221779.png]  
后面看了一些推荐算法，推荐使用栈来辅助完成  
这里记录一下就是为什么会想到用栈呢？  
栈数据结构简单，先进先出  
从前往后遍历入栈，当遇到待入栈元素比栈顶元素大的时候，栈顶元素出栈  
这是不是就对应着：找出某结点其后第一个最大的结点的值  
每一次出栈即意味着找到了他的“最大值”（其后第一个比他大的）  
但还有一点需要注意的是，需要记录出栈元素在原链表中的位置索引，因为需要输出对应的“最大值”数组  
所以引入了Java类库中的`Pair`，配对类，有一个key和一个value组成  
即在元素入栈的时候，就记录好该元素在原链表中的位置，这样出栈的时候，就很方便往目标数组中赋值

代码如下：

// 使用中间数据结构——栈 辅助解决，时间复杂度低
        public int[] nextLargerNodesByStack(ListNode head) { 
            if (head == null) { 
                return new int[0];
            }
            // 使用集合接受，可以避免一个遍历（查找长度）
            List<Integer> list = new ArrayList<>();
            int count = 0;
    
            // 引入了Pair配对类，一个key，一个value，因为这里需要记录原链表每个结点的索引和value
            Stack<Pair<Integer, Integer>> stack = new Stack<>();
    
            while (head != null) { 
                // 初始每个添加0，后出栈则相应更新
                list.add(0);
                while (!stack.empty() && head.val > stack.peek().getValue()) { 
                    // 栈不为空且待入栈元素大于栈顶元素，则栈顶元素出栈
                    Pair<Integer, Integer> pop = stack.pop();
                    list.set(pop.getKey(), head.val);
                }
                stack.push(new Pair<>(count, head.val));
                head = head.next;
                count++;
            }
    
            // List<Integer> 转 int[]
            return list.stream().mapToInt(Integer::intValue).toArray();
        }

LeetCode提交，通过  
![在这里插入图片描述][20190811193823919.png]  
下次类似”排序“算法，可以优先考虑是否可以使用栈辅助完成

记录一下：说明自己的算法道路还很长，继续加油

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWppdWppdTMz_size_16_color_FFFFFF_t_70]: /images/20211018/db555e6a786641cfbb9f55522590646c.png
[Link 1]: https://leetcode-cn.com/problems/next-greater-node-in-linked-list/
[20190811190221779.png]: /images/20211018/f5f0ed9ef2404ea1817c036ab435fa70.png
[20190811193823919.png]: /images/20211018/6bfa379341104e5bba74f0080966699b.png