• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode456. 132模式 | 132 Pattern

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note: n will be less than 15,000.

Example 1:

Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence. 

Example 2:

Input: [3, 1, 4, 2]

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2]. 

Example 3:

Input: [-1, 3, 2, 0]

Output: True

Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

给定一个整数序列:a1, a2, ..., an,一个132模式的子序列 ai, aj, ak 被定义为:当 i < j < k时,ai < ak < aj。设计一个算法,当给定有 n 个数字的序列时,验证这个序列中是否含有132模式的子序列。

注意:n 的值小于15000。

示例1:

输入: [1, 2, 3, 4]

输出: False

解释: 序列中不存在132模式的子序列。

示例 2:

输入: [3, 1, 4, 2]

输出: True

解释: 序列中有 1 个132模式的子序列: [1, 4, 2].

示例 3:

输入: [-1, 3, 2, 0]

输出: True

解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].

164ms
 1 struct Stack<T> {
 2     var items = [T]()
 3     mutating func push(item: T) {
 4         items.append(item)
 5     }
 6     mutating func pop() -> T {
 7         return items.removeLast()
 8     }
 9     func top() -> T {
10         return items.last!
11     }
12     func empty() -> Bool {
13         return items.count == 0
14     }
15 }
16 
17 class Solution {
18     func find132pattern(_ nums: [Int]) -> Bool {
19         var third = Int.min
20         var s = Stack<Int>()
21         for i in stride(from: nums.count - 1, through: 0, by: -1) {
22             if nums[i] < third {
23                 return true
24             }else {
25                 while !s.empty() && (nums[i] > s.top()) {
26                     third = s.top()
27                     _ = s.pop()
28                 }
29                 s.push(item: nums[i])
30             }
31         }
32         return false
33     }
34 }

324ms

 1 class Solution {
 2     func find132pattern(_ nums: [Int]) -> Bool {
 3         var hanoi = Array<Int>.init();
 4         var medNum = Int.min
 5         for index in stride(from: nums.count-1, through: 0, by: -1) {
 6             if nums[index] < medNum {
 7                 return true
 8             } else {
 9                 while (hanoi.count > 0 && hanoi.last! < nums[index]) {
10                     medNum = hanoi.last!
11                     hanoi.removeLast()
12                 }
13             }
14             hanoi.append(nums[index])
15         }
16         return false
17     }
18 }

1348ms

 1 class Solution {
 2     func find132pattern(_ nums: [Int]) -> Bool {
 3         if nums.count < 3{ 
 4             return false 
 5         }
 6         var newNums = [nums[0]]
 7         for i in 1..<nums.count {
 8             if nums[i] != nums[i-1]{
 9                 newNums.append(nums[i]);
10             }
11         }
12         if newNums.count < 3{ 
13             return false 
14         }
15         var minArr = [newNums[0]]
16         var min = newNums[0]
17         for i in newNums{
18             if i < min{
19                 min = i
20             }
21             minArr.append(min)
22         }
23         for i in 1..<newNums.count-1{
24             let a = minArr[i]
25             let b = newNums[i]
26             if a >= b{ 
27                 continue 
28             }
29             for j in (i+1)..<newNums.count{
30                 let c = newNums[j]
31                 if c > a && c < b {
32                     return true
33                 }
34             }
35         }
36         return false
37     }
38 }

4388ms

 1 class Solution {
 2     func find132pattern(_ nums: [Int]) -> Bool {
 3         if nums.count < 3 {
 4             return false
 5         }
 6         var i = nums.count
 7         var min = nums[i - 1]
 8         while (i > 0) {
 9             min = nums[i - 1]
10             var j = nums.count
11             var max = min
12             while (j > i) {
13                 let t = nums[j - 1]
14                 if t > min {
15                     if max > min {
16                         if t > max {
17                             return true
18                         }else {
19                             max = t
20                         }
21                     }else {
22                         max = t
23                     }
24                 }
25                 j = j - 1
26             }
27             i = i - 1
28         }
29         return false
30     }
31 }

6656ms

 1 class Solution {
 2     func find132pattern(_ nums: [Int]) -> Bool {
 3         var n:Int = nums.count
 4         var i:Int = 0
 5         var j:Int = 0
 6         var k:Int = 0
 7         while (i < n) {
 8             while (i < n - 1 && nums[i] >= nums[i + 1])
 9             {
10                 i += 1
11             }
12             j = i + 1;
13             while (j < n - 1 && nums[j] <= nums[j + 1])
14             {
15                  j += 1
16             }
17             k = j + 1
18             while (k < n) {
19                 if nums[k] > nums[i] && nums[k] < nums[j]
20                 {
21                      return true
22                 }
23                 k += 1
24             }
25             i = j + 1
26         }
27         return false
28     }
29 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift 1.8.0(Grizzly) 中region的理解 - A Globally Distributed Cluster发布时间:2022-07-13
下一篇:
[Swift]LeetCode868.二进制间距|BinaryGap发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap