IOS 算法(中级篇) ----- 132模式

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false,
其中:
n == nums.length
1 <= n <= 104
-109 <= nums[i] <= 109

例子:

输入：nums = [1,2,3,4]
输出：false
解释：序列中不存在 132 模式的子序列。

输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。

输入：nums = [-1,3,2,0]
输出：true
解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。

解题思路:

栈方法

题意不难理解留意下: 其中i < j < k 有 nums[i] < nums[k] < nums[j]

拆分一下, 如果有 2 > 3, 又找到 3 > 1, 根据传递性有 2 > 3 > 1 即有132模式子序列

按照这个思路, 我们用一个栈数组来维护3, 即中间数nums[k], 通过移入移出进行处理

例如:
[3,1,4,2], 我们先倒序处理下 [2, 4, 1, 3], (倒序比较好由大到小判断, 正序也可以)

i = 2, k = -1000000000, k < i, stack = []
i = 4, k = -1000000000, k < i, stack = [2], k = 2
i = 1, k = 2, k > i 直接返回 true

代码:

未翻译版

    func find132pattern(_ nums: [Int]) -> Bool {

        var k = -1000000000, stack = [Int]()
        
        for i in nums.reversed() {
            
            if k > i { return true }
            
            while let last = stack.last, last < i {
                k = stack.removeLast()
            }
            
            stack.append(i)
        }

        return false
    }

翻译版

    func find132pattern(_ nums: [Int]) -> Bool {

        // 定义中间元素k为最小值, 栈数组stack
        var k = -1000000000, stack = [Int]()
        
        // 倒序循环
        for i in nums.reversed() {
            
            // 如果找到 k > i 则返回
            if k > i { return true }
            
            // 另last为栈顶元素, 如果有 last < i, 进入循环
            // 进入这个循环始终能保证 j > k, 此时i可看做j
            // 找到满住条件成为k的值, 同时也会找出满足条件相对较大的k
            while let last = stack.last, last < i {
                // k为stack顶元素(后面元素, 因为是倒序) 移出stack栈顶元素继续循环
                k = stack.removeLast()
            }
            
            // 栈数组添加i
            stack.append(i)
        }

        // 没找到false返回
        return false
    }

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址