首页 > 其他分享 >力扣 334. 递增的三元子序列

力扣 334. 递增的三元子序列

时间:2023-07-07 14:55:05浏览次数:43  
标签:rightMax nums int 334 三元组 力扣 false 三元 leftMin

题目:

给你一个整数数组 nums ,判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ,使得 nums[i] < nums[j] < nums[k] ,返回 true ;否则,返回 false 。

 

示例 1:

输入:nums = [1,2,3,4,5]
输出:true
解释:任何 i < j < k 的三元组都满足题意
示例 2:

输入:nums = [5,4,3,2,1]
输出:false
解释:不存在满足题意的三元组
示例 3:

输入:nums = [2,1,5,0,4,6]
输出:true
解释:三元组 (3, 4, 5) 满足题意,因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
 

提示:

1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1
 

思路:

用到了空间换时间的思想

 

代码:

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        if(n < 3){
            return false;
        }
        vector<int> leftMin(n);
        vector<int> rightMax(n);
        leftMin[0] = nums[0];
        for(int i = 1; i < n; i++){
            leftMin[i] = min(leftMin[i - 1], nums[i]);
        }
        rightMax[n - 1] = nums[n - 1];
        for(int i = n - 2; i >= 0; i--){
            rightMax[i] = max(rightMax[i + 1], nums[i]);
        }
        for(int i = 1; i <= n - 2; i++){
            if(nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]){
                return true;
            }
        }
        return false;
    }
};

 

标签:rightMax,nums,int,334,三元组,力扣,false,三元,leftMin
From: https://www.cnblogs.com/yccy/p/17534972.html

相关文章

  • 力扣1. 两数之和
    问题:给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。 思考:1.利用暴力法......
  • [典·三元组]
    题目:MEX 来源:AtCoderBeginnerContest308根据例1可以先进行判断,如果根据E的不同情况进行统计的话方便入手1.从左到右统计M的{0,1,2}的情况2.从右到左统计X的{0,1,2}的情况3.判断当前s[i]为‘E’的情况下,并且对应的a[i]={0,1,2}三种情况相乘的个数(乘的是三元组的没出现的最......
  • 力扣 290 字母的是否符合规律规律
    #规律aabb;单词catcatdogdog;符合规律返回true。defwordPattern(规律:str,给定字符串:str):res=给定字符串.split()returnlist(map(规律.index,规律))==list(map(res.index,res))#验证result=wordPattern("aabb","catcatdogdoggg")print......
  • 关于力扣题的sql集训感悟
    在学习SQL的过程中,很多人都会选择参加力扣的SQL集训。力扣是一个面向程序员的在线编程平台,它提供了大量的算法题和数据库题,可以帮助我们提升编程能力和解决实际问题的能力。在参加力扣的SQL集训后,我有了一些感悟和收获,下面我将分享给大家。第一,系统学习和巩固SQL知识。力扣的SQL集......
  • 力扣之旅-0级小白到1级小白
    0到1是一个巨大的进步!海明威说过:“优于别人并不高贵,真正的高贵是优于过去的自己“目录:引言开始的挫折与挑战寻找解题思路和技巧持之以恒与刻意练习克服困难和失败的心态高效学习和准备复习寻求帮助和合作成功的喜悦与未来计划1、引言力扣是一个在线编程挑战平台,提供了广泛的算法和......
  • 力扣217题
    #给你一个整数数组nums。#如果任一值在数组中出现至少两次,返回true;#如果数组中每个元素互不相同,返回false。defremove_dup(nums):unique_nums=list(set(nums))returnunique_numsdefis_xiangdeng(nums):result=remove_dup(nums)ifnums==result:......
  • 力扣---1253. 重构 2 行二进制矩阵
    给你一个 2 行 n 列的二进制数组:矩阵是一个二进制矩阵,这意味着矩阵中的每个元素不是 0 就是 1。第 0 行的元素之和为 upper。第 1 行的元素之和为 lower。第 i 列(从 0 开始编号)的元素之和为 colsum[i],colsum 是一个长度为 n 的整数数组。你需要利用 ......
  • 力扣---53. 最大子数组和
    给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。子数组 是数组中的一个连续部分。 示例1:输入:nums=[-2,1,-3,4,-1,2,1,-5,4]输出:6解释:连续子数组 [4,-1,2,1]的和最大,为 6。示例2:输入:nums=[1]输出:1示例3......
  • 力扣---1186. 删除一次得到子数组最大和
    给你一个整数数组,返回它的某个 非空 子数组(连续元素)在执行一次可选的删除操作后,所能得到的最大元素总和。换句话说,你可以从原数组中选出一个子数组,并可以决定要不要从中删除一个元素(只能删一次哦),(删除后)子数组中至少应当有一个元素,然后该子数组(剩下)的元素总和是所有子数组之中最......
  • 力扣---2485. 找出中枢整数
    给你一个正整数 n ,找出满足下述条件的 中枢整数 x :1 和 x 之间的所有元素之和等于 x 和 n 之间所有元素之和。返回中枢整数 x 。如果不存在中枢整数,则返回 -1 。题目保证对于给定的输入,至多存在一个中枢整数。 示例1:输入:n=8输出:6解释:6是中枢整数,因......