热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

[Swift]LeetCode1019:链表中每个节点的下一个更大值|NextGreaterNodeinLinkedListAnalysis

本文详细分析了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_inext_larger(node_i) is the node_j.val such that j > inode_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. 1 <= node.val <= 10^9 for each node in the linked list.
  2. 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. 对于链表中的每个节点,1 <= node.val <= 10^9
  2. 给定列表的长度在 [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 }

 


推荐阅读
author-avatar
DarkBaron_
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有