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

相关推荐

  • leetcode454-四数相加II

    原题 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。 为…

    算法 2019年12月27日
    070
  • leetcode297-二叉树的序列化与反序列化

    原题 序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。…

    算法 2020年1月15日
    0100
  • leetcode739-每日温度

    原题 根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。 例如,给定一个列表 te…

    算法 2019年12月11日
    0130
  • leetcode238-除自身以外数组的乘积

    原题 给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积…

    算法 2020年6月4日
    070
  • leetcode111-二叉树的最小深度

    原题 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,nul…

    算法 2020年3月25日
    0210
  • 蓝桥杯试题-小数第n位

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

    算法 2020年2月29日
    080
  • leetcode128-最长连续序列

    原题 给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示例: 输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长…

    算法 2020年6月6日
    090
  • leetcode55-跳跃游戏

    原题 原题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例1: 输入: [2,3,1…

    算法 2020年2月9日
    060
  • leetcode69-x的平方根

    原题 实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例1: 输入:…

    算法 2019年12月30日
    040
  • leetcode155-最小栈

    原题 设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。 pop() – 删除栈顶的元素。 top() …

    算法 2019年12月11日
    0110

发表回复

登录后才能评论