|
Zeal without knowledge is fire without light.
没有知识的热忱犹如火之无光。 问题描述给一个链表，返回每个节点下一个比他大的值，如果不存在就返回0 。
示例 1： 输入：[2,1,5] 输出：[5,5,0] 解释：2的下一个比他大的是5，1的下一个比他大的也是5，5后面没有比他大的值，所以是0。
示例 2： 输入：[2,7,4,3,5] 输出：[7,0,5,5,0]
示例 3： 输入：[1,7,5,1,9,2,5,1] 输出：[7,9,9,9,0,5,0,0]
问题分析这题和382，每日温度的5种解题思路很像，不过有点不同的是第382题求的是下一个比他大的数的位置和当前数位置的差值，而这里求的是下一个比他大的数的值。还有一点是382题使用的是数组，我们这道题使用的是链表。 所以我们完全可以参照382题的做法，由于链表访问比较麻烦，需要从前往后一个个遍历，我们这里直接把链表转化为list集合的方式来求解。我们不把链表转为数组，因为数组需要先声明大小，而链表的大小我们是不知道的（如果先计算链表的长度再转化为数组感觉有点多余），我们直接把链表转化为list集合，这样会更方便些。解题思路完全可以参照第382题，我们来看下代码 1public int[] nextLargerNodes(ListNode head) {
2 List<Integer> list = new ArrayList<>();
3 //链表元素存储到集合中
4 while (head != null) {
5 list.add(head.val);
6 head = head.next;
7 }
8 int[] res = new int[list.size()];
9 for (int i = 0; i < list.size() - 1; i++) {
10 for (int j = i + 1; j < list.size(); j++) {
11 if(list.get(j)>list.get(i)){
12 res[i]=list.get(j);
13 break;
14 }
15 }
16 }
17 return res;
18}
1public int[] nextLargerNodes(ListNode head) {
2 List<Integer> list = new ArrayList<>();
3 //链表元素存储到集合中
4 while (head != null) {
5 list.add(head.val);
6 head = head.next;
7 }
8 //栈中存储的是元素的下标，并且从栈底到栈顶元素在集合中对应的
9 //值是从大到小的
10 Stack<Integer> stack = new Stack<>();
11 int[] res = new int[list.size()];
12 for (int i = 0; i < list.size(); i++) {
13 while (!stack.empty() && list.get(stack.peek()) < list.get(i)) {
14 //如果栈顶元素对应的值小于当前值，说明栈顶元素遇到了比他小的
15 int index = stack.pop();
16 res[index] = list.get(i);
17 }
18 stack.push(i);
19 }
20 return res;
21}
1public int[] nextLargerNodes(ListNode head) {
2 List<Integer> list = new ArrayList<>();
3 //链表元素存储到集合中
4 while (head != null) {
5 list.add(head.val);
6 head = head.next;
7 }
8 int[] res = new int[list.size()];
9 for (int i = res.length - 1; i >= 0; i--) {
10 int j = i + 1;
11 int num = 0;
12 if (j < res.length)
13 num = list.get(j);
14 while (j < res.length) {
15 if (num > list.get(i)) {
16 //如果找到就停止while循环
17 res[i] = num;
18 break;
19 } else if (num == 0) {
20 break;
21 } else {
22 num = res[j++];
23 }
24 }
25 }
26 return res;
27}
上面3种解法我们完全是参照第382题的答案写的，并且在计算之前都首先把链表转化为list集合，我们能不能直接使用链表，不把他转化为list集合呢，其实也是可以的，我们只需要使用一个栈来存储链表中每个节点在list中的位置即可，并且栈中元素在集合list中对应的值从栈底到栈顶是递减的，原理还是和上面类似，我们就以上面例二的数据[2,7,4,3,5]来画个图看一下是怎么样的一个实现过程 
我们来看下代码
1public int[] nextLargerNodes(ListNode head) {
2 List<Integer> list = new ArrayList<>();
3 Stack<Integer> stack = new Stack();
4 for (ListNode node = head; node != null; node = node.next) {
5 while (!stack.isEmpty() && node.val > list.get(stack.peek())) {
6 list.set(stack.pop(), node.val);
7 }
8 stack.push(list.size());
9 list.add(node.val);
10 }
11 for (int i : stack) {
12 list.set(i, 0);
13 }
14 int[] res = new int[list.size()];
15 for (int i = 0; i < res.length; i++) {
16 res[i] = list.get(i);
17 }
18 return res;
19}
上面代码核心部分在4-10行，原理和前几种写法类似，14-17行是把list转化为数组，第11-13行遍历这个栈，这个时候栈中的每个元素在list中对应的值在后面没有比他更大的，我们直接让他等于0即可。
当然我们还可以改为递归的方式，有兴趣的可以自己看下
1int[] res;
2
3public int[] nextLargerNodes(ListNode head) {
4 calNode(head, 0, new Stack<>());
5 return res;
6}
7
8public void calNode(ListNode node, int index, Stack<Integer> stack) {
9 if (node == null) {
10 res = new int[index];//初始化数组的大小
11 return;
12 }
13 calNode(node.next, index + 1, stack);
14 while (!stack.empty() && stack.peek() <= node.val)
15 stack.pop();
16 res[index] = stack.empty() ? 0 : stack.peek();
17 stack.push(node.val);
18}
注意这里的第14行如果栈顶元素不小于当前值就要出栈，一直到栈顶元素大于当前值为止，为什么要这样写，因为这里的递归对链表的访问实际上相当于从链表的尾到头开始的，也就是逆序。这个可以参照前面的剪枝计算，因为他也在集合中从后往前开始计算的。
|
