资讯专栏INFORMATION COLUMN

132pattern

Raaabbit / 3178人阅读

摘要:记录即之前,里的最小值,即题目里的即所有不满足的直接跳过。已知那么找一个比大,又尽可能小的数找满足就最可能。找到后,比较是否满足满足就返回更新栈顶元素,表示表示

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.

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].

public class Solution {
    public boolean find132pattern(int[] nums) {
        int[] arr = Arrays.copyOf(nums, nums.length);
        
        for(int i=1; i= 0; j--) {
            // ai < ak < aj 即 ai< aj 所有不满足的直接跳过。
            if(nums[j] <= arr[j]) continue;
            // 已知ai, 那么找一个比ai大,又尽可能小的数ak, 找满足ai arr[top]) return true;
            // 更新栈顶元素ak, top++表示pop, --top表示push
            arr[--top] = nums[j];
        }
        
        return false;
    }

}
//  1 3 5 0 3 6  aj
//  1 1 1 0 0 0  ai
//  0 0 0 0 3 6  ak

//   https://discuss.leetcode.com/topic/68242/java-solutions-from-o-n-3-to-o-n-for-132-pattern/2

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/66561.html

相关文章

  • LeetCode[132] Pattern

    摘要:复杂度思路维护一个里面有最大值和最小值。如果当前值小于的最小值,那么就将原来的压进去栈,然后在用这个新的的值再进行更新。如果没有适合返回的值,就重新更新当前的。 Leetcode[132] Pattern Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak ...

    go4it 评论0 收藏0
  • 【实践】玩转正则表达式+JS正则处理函数

    摘要:前言写这篇文章不是空穴来风,最近一个礼拜写了一个简单的脚本,用来处理上千个文件,以便于在某些特定字符的周围添加标记,先说一下我这个脚本使用场景主要是来识别中文具体做什么,之后会单独写一篇文章,此处只提该脚本作用,同时为不同的文件类型,包括, 前言 写这篇文章不是空穴来风,最近一个礼拜写了一个简单的nodejs脚本,用来处理上千个文件,以便于在某些特定字符的周围添加标记,先说一下我这个脚...

    DoINsiSt 评论0 收藏0
  • php之正则表达式函数总结

    摘要:之正则表达式函数总结匹配用于匹配常用的函数有两个,分别是和看代码一般三个参数正则需要匹配的字符串因为匹配到了个就会停止匹配将所有满足正则规则的匹配放到数组里。 php之正则表达式函数总结 匹配 用于匹配常用的函数有两个,分别是preg_match和preg_match_all 看代码: //preg_match($pattern, $subject, &$match, [$flag...

    sshe 评论0 收藏0
  • java 验证手机号码、电话号码(包括最新的电信、联通和移动号码)

    摘要:目前的号码段更新代码座机电话格式验证中国电信号码格式验证手机段中国联通号码格式验证手机段简单手机号码校验,校验手机号码的长度和开头中国移动号码格式验证手机段仅手机号格式校验手机和座机号格式校验匹配多个号码以或空格隔开的格 目前的号码段(2017-06-01更新)showImg(https://segmentfault.com/img/bVSd9C?w=862&h=147); java...

    lanffy 评论0 收藏0

发表评论

0条评论

Raaabbit

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<