leetcode456-132模式

原题

给定一个整数序列: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].

解法

思想

  1. 暴力,从尾向头遍历,如果当前元素是132中的最后一个元素,则前面和中间一定分别有一个小于当前元素的元素和一个大于当前元素的元素。

  2. 栈,参考 https://leetcode-cn.com/problems/132-pattern/solution/132mo-shi-by-leetcode-2/

代码

  1. 暴力
class Solution {
    public boolean find132pattern(int[] nums) {
        for(int i = nums.length-1;i>=2;i--){
            int tail = nums[i];
            boolean hasPeek = false;
            for(int j = i-1;j>=0;j--){
                if(nums[j]>tail) hasPeek = true;
                else if(hasPeek&&nums[j]<tail) return true;
            }
        }
        return false;
    }
}
public class Solution {
    public boolean find132pattern(int[] nums) {
        if (nums.length < 3)
            return false;
        Stack<Integer> stack = new Stack<>();
        int[] min = new int[nums.length];
        min[0] = nums[0];
        for (int i = 1; i < nums.length; i++)
            min[i] = Math.min(min[i - 1], nums[i]);
        for (int j = nums.length - 1; j >= 0; j--) {
            if (nums[j] > min[j]) {
                while (!stack.isEmpty() && stack.peek() <= min[j])
                    stack.pop();
                if (!stack.isEmpty() && stack.peek() < nums[j])
                    return true;
                stack.push(nums[j]);
            }
        }
        return false;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode456-132%e6%a8%a1%e5%bc%8f/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月29日 16:25
下一篇 2020年1月30日 16:08

相关推荐

  • leetcode652-寻找重复的子树

    原题 给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。 两棵树重复是指它们具有相同的结构以及相同的结点值。 示例1: 1 / \ 2…

    算法 2019年12月26日
    0310
  • leetcode73-矩阵置零

    原题 给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1: 输入: [   [1,1,1],  …

    算法 2020年5月14日
    080
  • leetcode705-设计哈希集合

    原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说,你的设计应该包含以下的功能 add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合…

    算法 2019年12月18日
    0140
  • 剑指offer06-从尾到头打印链表

    原题(来源Leetcode) 输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。 示例1: 输入: head = [1,3,2] 输出: [2,3,1] 限制: …

    算法 2020年4月10日
    050
  • leetcode543-二叉树的直径

    原题 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例: 给定二叉树 1 / \ 2 3 / \ 4 5…

    算法 2020年3月10日
    0210
  • leetcode236-二叉树的最近公共祖先

    原题 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 …

    2020年1月15日
    060
  • leetcode70-爬楼梯

    原题 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意: 给定 n 是一个正整数。  示例 1: 输入:…

    算法 2020年1月21日
    0840
  • leetcode199-二叉树的右视图

    原题 给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例: 输入: [1,2,3,null,5,null,4] 输出:&nb…

    算法 2020年4月22日
    0110
  • leetcode701-二叉搜索树中的插入操作

    原题 给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。 注意,可能存在多种有效的插入方式,只…

    算法 2020年1月16日
    0100
  • 蓝桥杯试题-小数第n位

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。  如果我们把有限小数的末尾加上无限多个…

    算法 2020年2月29日
    080

发表回复

登录后才能评论