作者：DarkBaron_ | 来源：互联网 | 2024-10-24 00:34
本文详细分析了LeetCode1019题目“链表中每个节点的下一个更大值”，探讨了如何在链表中找到每个节点右侧第一个比其值更大的节点。通过使用栈的数据结构，我们可以高效地解决这一问题，并提供了详细的代码实现和复杂度分析。
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10634379.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
热烈欢迎，请直接点击！！！
进入博主App Store主页，下载使用各个作品！！！
注：博主将坚持每月上线一个新app！！！
We are given a linked list with head as the first node. Let's number the nodes in the list: node_1, node_2, node_3, ... etc.
Each node may have a next larger value: for node_i, next_larger(node_i) is the node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible choice. If such a j does not exist, the next larger value is 0.
Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).
Note that in the example inputs (not outputs) below, arrays such as [2,1,5] represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.
Example 1:
Input: [2,1,5]
Output: [5,5,0]
Example 2:
Input: [2,7,4,3,5]
Output: [7,0,5,5,0]
Example 3:
Input: [1,7,5,1,9,2,5,1]
Output: [7,9,9,9,0,5,0,0]
Note:
-
1 <= node.val <= 10^9 for each node in the linked list.
- The given list has length in the range
[0, 10000].
给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。
每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。
返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。
注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。
示例 1：
输入：[2,1,5]
输出：[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]
提示：
- 对于链表中的每个节点，
1 <= node.val <= 10^9
- 给定列表的长度在
[0, 10000] 范围内
552ms
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * public var val: Int
5 * public var next: ListNode?
6 * public init(_ val: Int) {
7 * self.val = val
8 * self.next = nil
9 * }
10 * }
11 */
12 class Solution {
13 func nextLargerNodes(_ head: ListNode?) -> [Int] {
14 guard let head = head else { return [] }
15 var result = [0]
16 var stack = [(0, head)]
17 while let (lastIdx, lastNode) = stack.last, let curr = lastNode.next {
18 result.append(0)
19 if curr.val > lastNode.val {
20 while stack.count > 0 {
21 if let (idx, listNode) = stack.last, curr.val > listNode.val {
22 stack.removeLast()
23 result[idx] = curr.val
24 } else {
25 break
26 }
27 }
28 }
29 stack.append((lastIdx + 1, curr))
30 }
31 return result
32 }
33 }
604ms
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * public var val: Int
5 * public var next: ListNode?
6 * public init(_ val: Int) {
7 * self.val = val
8 * self.next = nil
9 * }
10 * }
11 */
12 class Solution {
13 func nextLargerNodes(_ head: ListNode?) -> [Int] {
14 guard let head = head else { return [] }
15
16 var results = [Int]()
17 var curr: ListNode? = head
18 while curr != nil {
19 results.append(0)
20 curr = curr?.next
21 }
22
23 var stack = [(Int, Int)]()
24
25 curr = head
26 var i = 0
27 while let this = curr {
28 while let last = stack.last, this.val > last.1 {
29 stack.removeLast()
30 results[last.0] = this.val
31 }
32
33 stack.append((i, this.val))
34 i += 1
35 curr = this.next
36 }
37
38 return results
39 }
40 }
636ms
1 class Solution {
2 func nextLargerNodes(_ head: ListNode?) -> [Int] {
3 var arr = [Int]()
4 var node = head
5 while let n = node {
6 arr.append(n.val)
7 node = n.next
8 }
9 var stack = Stack()
10 var ans = [Int](repeating: 0, count: arr.count)
11 for (index, num) in arr.enumerated().reversed() {
12 while let top = stack.top(),
13 top <= num {
14 stack.pop()
15 }
16 if let top = stack.top() {
17 ans[index] = top
18 }
19 stack.push(num)
20 }
21 return ans
22 }
23 }
24
25 struct Stack {
26 private var arr = [Int]()
27 init() {}
28 var count: Int {
29 return arr.count
30 }
31 var isEmpty: Bool {
32 return arr.isEmpty
33 }
34 mutating func push(_ n: Int) {
35 arr.append(n)
36 }
37 func top() -> Int? {
38 return arr.last
39 }
40 mutating func pop() -> Int? {
41 if isEmpty { return nil }
42 return arr.removeLast()
43 }
44 }
644ms
1 class Solution {
2 func length(_ head:ListNode?) -> Int
3 {
4 var curr = head
5 var count = 0
6 while curr != nil
7 {
8 curr = curr?.next
9 count += 1
10 }
11 return count
12 }
13
14 func nextLargerNodes(_ head: ListNode?) -> [Int] {
15 if head == nil
16 {
17 return []
18 }
19 if head?.next == nil
20 {
21 return [0]
22 }
23
24 var curr = head
25
26 var len = length(head)
27
28 var list : [Int] = []
29
30 var stk = Stack()
31
32 while curr != nil
33 {
34 while !stk.isEmpty() && stk.peek().val .val
35 {
36 var poppedItem = stk.pop()
37 poppedItem.val = curr!.val
38 }
39 stk.push(curr!)
40 curr = curr?.next
41 }
42
43 while !stk.isEmpty()
44 {
45 stk.pop().val = 0
46 }
47
48 curr = head
49 while curr != nil
50 {
51 list.append(curr!.val)
52 curr = curr?.next
53 }
54 return list
55 }
56 }
57
58 struct Stack
59 {
60 var elements:[T] = []
61 mutating func push(_ item:T)
62 {
63 elements.append(item)
64 }
65 mutating func pop() -> T
66 {
67 return elements.removeLast()
68 }
69 func isEmpty() -> Bool
70 {
71 return elements.isEmpty
72 }
73 func peek() -> T
74 {
75 return elements.last!
76 }
77 }
Runtime: 764 ms
Memory Usage: 21.3 MB
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * public var val: Int
5 * public var next: ListNode?
6 * public init(_ val: Int) {
7 * self.val = val
8 * self.next = nil
9 * }
10 * }
11 */
12 class Solution {
13 var ret:[Int] = [Int]()
14 var d:[(Int,Int)] = [(Int,Int)]()
15 var ans:[Int] = [Int]()
16
17 func nextLargerNodes(_ head: ListNode?) -> [Int] {
18 var head = head
19 while(head != nil)
20 {
21 ret.append(head!.val)
22 head = head?.next
23 }
24 for i in stride(from:ret.count - 1,through:0,by:-1)
25 {
26 while(d.count != 0 && d.first!.0 <= ret[i])
27 {
28
29 d.removeFirst()
30 }
31 if d.count != 0
32 {
33 ans.append(d.first!.0)
34 }
35 else
36 {
37 ans.append(0)
38 }
39 d.insert((ret[i],i),at:0)
40 }
41 return ans.reversed()
42 }
43 }
![扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]](https://img.php1.cn/3c972/245b5/42f/19446f78530d3747.jpeg)
京公网安备 11010802041100号