★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★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: FalseExplanation: There is no 132 pattern in the sequence.
Example 2:
Input: [3, 1, 4, 2]Output: TrueExplanation: There is a 132 pattern in the sequence: [1, 4, 2].
Example 3:
Input: [-1, 3, 2, 0]Output: TrueExplanation: 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{ 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 == 014 }15 }16 17 class Solution {18 func find132pattern(_ nums: [Int]) -> Bool {19 var third = Int.min20 var s = Stack ()21 for i in stride(from: nums.count - 1, through: 0, by: -1) {22 if nums[i] < third {23 return true24 }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 false33 }34 }
324ms
1 class Solution { 2 func find132pattern(_ nums: [Int]) -> Bool { 3 var hanoi = Array .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 false17 }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.. = b{ 27 continue 28 }29 for j in (i+1).. a && c < b {32 return true33 }34 }35 }36 return false37 }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.count11 var max = min12 while (j > i) {13 let t = nums[j - 1]14 if t > min {15 if max > min {16 if t > max {17 return true18 }else {19 max = t20 }21 }else {22 max = t23 }24 }25 j = j - 126 }27 i = i - 128 }29 return false30 }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 += 111 }12 j = i + 1;13 while (j < n - 1 && nums[j] <= nums[j + 1])14 {15 j += 116 }17 k = j + 118 while (k < n) {19 if nums[k] > nums[i] && nums[k] < nums[j]20 {21 return true22 }23 k += 124 }25 i = j + 126 }27 return false28 }29 }