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

原题链接：

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

https://leetcode.cn/problems/next-greater-node-in-linked-list/description/

完成情况：

参考代码(1)：

package 西湖算法题解___中等题02;

import java.util.ArrayDeque;
import java.util.Deque;

public class __1019链表中的下一个更大节点__遍历 {
	public class ListNode {
		int val;
		ListNode next;
		ListNode() {}
		ListNode(int val) { this.val = val; }
		ListNode(int val, ListNode next) { this.val = val; this.next = next; }
	}

	/**
	 给定一个长度为 n 的链表 head
	 对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。
	 返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。

	 就是说，每个节点都去返回后面比它大，且最大的节点的值。
	 如果不存在这样一个节点，那么则返回0

	 * @param head
	 * @return
	 */
	private int[] ans;
	private final Deque<Integer> monotonicStack = new ArrayDeque<>();   //单调栈（节点）
	public int[] nextLargerNodes(ListNode head) {
		findStack(head,0);
		return ans;
	}

	private void findStack(ListNode node,int i){
		if (node == null){
			ans = new int[i];   // i 就是链表长度
			return;
		}
		findStack(node.next,i+1);
		while (!monotonicStack.isEmpty() && monotonicStack.peek() <= node.val){
			monotonicStack.pop();   // 弹出无用数据
		}
		if (!monotonicStack.isEmpty()){
			ans[i] = monotonicStack.peek(); //栈顶就是第i个节点的下一个更大的元素
		}
		monotonicStack.push(node.val);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

参考代码(2)：

package 西湖算法题解___中等题02;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

public class __1019链表中的下一个更大节点__翻转链表 {

	public class ListNode {
		int val;
		ListNode next;
		ListNode() {}
		ListNode(int val) { this.val = val; }
		ListNode(int val, ListNode next) { this.val = val; this.next = next; }
	}


	private int n;
	/**
	 *
	 * @param head
	 * @return
	 */
	public int[] nextLargerNodes(ListNode head) {
		head = reverseList(head);
		int [] ans = new int[n];
		Deque<Integer> monotonicStack = new ArrayDeque<Integer>();
		for (ListNode curNode = head;curNode != null;curNode = curNode.next){
			while (!monotonicStack.isEmpty() && monotonicStack.peek() <= curNode.val){
				monotonicStack.pop();   //弹出无用的数据
			}
			ans[--n] = (monotonicStack.isEmpty() ? 0:monotonicStack.peek());
			monotonicStack.push(curNode.val);
		}
		return ans;
	}

	/**
	 * 反转链表
	 * @param head
	 * @return
	 */
	private ListNode reverseList(ListNode head) {
		ListNode pre = null,cur = head;
		while (cur != null){
			ListNode next = cur.next;
			cur.next = pre;
			pre = cur;
			cur = next;
			n++;
		}
		return pre;
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

参考代码(3)：

package 西湖算法题解___中等题02;

import java.util.ArrayDeque;
import java.util.Deque;

public class __1019链表中的下一个更大节点__用每个数更新其它数的下一个更大元素 {
	public class ListNode {
		int val;
		ListNode next;
		ListNode() {}
		ListNode(int val) { this.val = val; }
		ListNode(int val, ListNode next) { this.val = val; this.next = next; }
	}


	/**
	 *
	 * @param head
	 * @return
	 */
	public int[] nextLargerNodes(ListNode head) {
		int n = 0;
		for (ListNode curNode = head;curNode != null;curNode = curNode.next){
			n++;    //确定返回值的长度
		}
		int [] ans = new int[n];
		Deque<int []> monotonicStack = new ArrayDeque<int []>();    //单调栈（节点值、节点下标）
		int index = 0;
		for (ListNode curNode = head;curNode != null;curNode = curNode.next){
			while (!monotonicStack.isEmpty() && monotonicStack.peek()[0] < curNode.val){
				ans[monotonicStack.pop()[1]] = curNode.val;     //用当前节点值更新答案
			}
			monotonicStack.push(new int[]{curNode.val,index++});
		}
		return ans;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

参考代码(4)：

package 西湖算法题解___中等题02;

import java.util.ArrayDeque;
import java.util.Deque;

public class __1019链表中的下一个更大节点__用每个数更新其它数的下一个更大元素__优化 {
	public class ListNode {
		int val;
		ListNode next;
		ListNode() {}
		ListNode(int val) { this.val = val; }
		ListNode(int val, ListNode next) { this.val = val; this.next = next; }
	}

	/**
	 *
	 * @param head
	 * @return
	 */
	public int[] nextLargerNodes(ListNode head) {
		int n = 0;
		for (ListNode curNode = head;curNode != null ;curNode = curNode.next){
			n++;    //确定返回值的长度
		}
		int ans [] = new int[n];
		Deque<Integer> monotonicStack = new ArrayDeque<Integer>();      //Integer类型，Deque结构。
		int index = 0;
		for (ListNode curNode = head;curNode != null ;curNode = curNode.next){
			while (!monotonicStack.isEmpty() && ans[monotonicStack.peek()] < curNode.val){
				ans[monotonicStack.pop()] = curNode.val;
			}
			monotonicStack.push(index);
			ans[index++] = curNode.val;
		}
		for (int idx : monotonicStack){
			ans[idx] = 0;
		}
		return ans;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41