​LeetCode刷题实战456：132 模式

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 132 模式，我们先来看题面：

https://leetcode-cn.com/problems/132-pattern/

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j]. Return true if there is a 132 pattern in nums, otherwise, return false.

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

示例

示例 1：

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

示例 2：

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

示例 3：

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

解题

原题中说明，要存在132的模式，那么数组之内就一定要有至少三个数才行。因此我们要在数组长度大于2的情况下找出符合132模式的子数组，再直接返回真，其余情况（找不到132模式的子数组的时候）返回假。需要至少三个变量，yi、er和san分别代表第一个、第二个和到三个数。初始状态下，yi先取坐标为0的数字，因为无论如何，yi在三个数中都必须是坐标最小的。er从yi的右边开始取，这时为了保证最大可能性能取到符合要求的子数组，因此yi必须尽可能小，也就是说，每一次er的坐标变化后，yi都要更新为er左边最小的数。并且每一次取了yi和er的值后，都要判断满足yi小于er。yi和er都初定后，开始从er的右边给san取值，只要找到san的值介于yi和er之间的，就返回真。

class Solution {
    public boolean find132pattern(int[] nums) {
        int l=nums.length;
        if(l>2){
            int yi=nums[0];//第一个数
            int san=0;//第三个数
            for(int i=1;i<l;i++){
                int er=nums[i];//第二个数
                yi=Math.min(yi,nums[i-1]);//第一个数要始终是er左边的最小值
                if(yi>er){
                    continue;
                }
                for(int j=i+1;j<l;j++){
                    san=nums[j];
                    if(er>san&&san>yi){
                        return true;
                    }
                }
            } 
        }return false;
    }
}

上期推文：

LeetCode1-440题汇总，希望对你有点帮助！

LeetCode刷题实战441：排列硬币

LeetCode刷题实战442：数组中重复的数据

LeetCode刷题实战443：压缩字符串

LeetCode刷题实战444：序列重建

LeetCode刷题实战445：两数相加 II

LeetCode刷题实战446：等差数列划分 II - 子序列

LeetCode刷题实战447：回旋镖的数量

LeetCode刷题实战448：找到所有数组中消失的数字

LeetCode刷题实战449：序列化和反序列化二叉搜索树

LeetCode刷题实战450：删除二叉搜索树中的节点

LeetCode刷题实战451：根据字符出现频率排序

LeetCode刷题实战452：用最少数量的箭引爆气球

LeetCode刷题实战453：最小操作次数使数组元素相等

LeetCode刷题实战454：四数相加 II

LeetCode刷题实战455：分发饼干