[Swift]LeetCode1019.链表中的下一个更大节点|NextGreaterNodeInLinkedList ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（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<ListNode>()
31         
32         while curr != nil
33         {
34             while !stk.isEmpty() && stk.peek().val < curr!.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<T>
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 }