[Swift]LeetCode334.递增的三元子序列|IncreasingTripletSubsequence

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

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

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10261970.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

Input: [1,2,3,4,5]
Output: true

Example 2:

Input: [5,4,3,2,1]
Output: false

给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。

数学表达式如下:

如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1，
使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。

说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。

示例 1:

输入: [1,2,3,4,5]
输出: true

示例 2:

输入: [5,4,3,2,1]
输出: false

16ms

 1 class Solution {
 2     func increasingTriplet(_ nums: [Int]) -> Bool {
 3         guard nums.count >= 3 else {
 4             return false
 5         }
 6         
 7         var first = Int.max
 8         var second = Int.max
 9         
10         for num in nums {
11             if num <= first {
12                 first = num
13             } else if num <= second {
14                 second = num
15             } else {
16                 return true
17             }
18         }
19         return false
20     }
21 }

20ms

 1 class Solution {
 2        func increasingTriplet(_ nums: [Int]) -> Bool {
 3    
 4     guard nums.count >= 3 else {
 5       
 6       return false
 7     }
 8     
 9     var minvalue = nums[0]
10     
11     var middle = Int.max
12     
13     var minvalue1 = nums[0]
14     
15     for i in 1..<(nums.count - 1) {
16       
17       if nums[i] <= minvalue1 {
18         
19         if middle != Int.max {
20           
21           minvalue1 = nums[i]
22         }
23         else {
24           
25           minvalue = nums[i]
26           
27           minvalue1 = minvalue
28           
29           middle = Int.max
30         }
31       }
32       else if nums[i] <= middle {
33         
34         middle = nums[i]
35         
36         minvalue = minvalue1
37       }
38       else {
39         
40         return true
41       }
42     }
43     
44     return minvalue < middle && middle < nums.last!
45   }
46 }

48ms

 1 class Solution {
 2     func increasingTriplet(_ nums: [Int]) -> Bool {
 3         if nums.count < 3 {
 4             return false
 5         }
 6         var minI = nums[0]
 7         var bigMin : Int? = nil
 8         
 9         for i in 1..<nums.count {
10             if bigMin != nil && nums[i] > bigMin! {
11                 return true
12             }
13             
14             if nums[i] < minI {
15                 minI = nums[i]
16             }
17             if nums[i] > minI {
18                 if bigMin == nil {
19                     bigMin = nums[i]
20                 }else {
21                     bigMin = min(nums[i], bigMin!)
22                 }
23             }
24         }
25         
26         return false
27     }
28 }

56ms

 1 class Solution {
 2     func increasingTriplet(_ nums: [Int]) -> Bool {
 3         var minInt:Int = Int.max
 4         var maxInt:Int = Int.max
 5         for item in nums {
 6             if minInt >= item {
 7                 minInt = item
 8             }else if maxInt >= item {
 9                 maxInt = item
10             }else{
11                 return true
12             }
13         }
14         return false
15     }
16 }

56ms

 1 class Solution {
 2     func increasingTriplet(_ nums: [Int]) -> Bool {
 3         guard nums.count > 2 else {
 4             return false
 5         }
 6 
 7         var n1 = Int.max
 8         var n2 = Int.max - 1
 9 
10         for n in nums {
11             if n <= n1 {
12                 n1 = n
13             } else if n < n2 {
14                 n2 = n
15             } else if n1 < n2 && n2 < n {
16                 return true
17             }
18         }
19         
20         return false
21     }
22 }