美文网首页leetcode
334. 递增的3元子序列

334. 递增的3元子序列

作者: geaus | 来源:发表于2020-02-10 16:33 被阅读0次

    题目描述

    给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列。
    说明: 要求算法的时间复杂度为 O(n),空间复杂度为 O(1) 。

    示例 1:
    
    输入: [1,2,3,4,5]
    输出: true
    示例 2:
    
    输入: [5,4,3,2,1]
    输出: false
    

    解题思路

    设置两个数small、mid。遍历数组时,当ai比small小时,更新small;否则ai比mid小时,更新mid(此时仍有small<mid);否则说明找到了三元序列的第三个数直接返回true。若遍历完数组仍未找到则返回false。

        bool increasingTriplet(vector<int>& nums) {
            int small = numeric_limits<int>::max();
            int mid = numeric_limits<int>::max();
    
            for(int i=0; i<nums.size(); i++){
                if(small>=nums[i])
                    small = nums[i];
                else if(mid>=nums[i])
                    mid = nums[i];
                else
                    return true;
            }
    
            return false;
        }
    

    相关文章

      网友评论

        本文标题:334. 递增的3元子序列

        本文链接:https://www.haomeiwen.com/subject/sznaxhtx.html