文档章节

334. Increasing Triplet Subsequence

cofama
 cofama
发布于 2017/04/26 12:39
字数 533
阅读 20
收藏 0

原题链接

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

题目的意思是判断数组中是否存在三个数的递增数列,这三个数不要求是相邻的,比如[1,4,2,7,5]中1、2、5就是符合要求的数列。

我分别用start和mid来记录数列中最小值和中间值的候选值。这两个值都初始为INT_MAX。遍历数组,比较当前数组元素与start的大小,由于第一个元素肯定比INT_MAX小,所以实际上start初始为首元素。接着遍历,如果当前元素比start小,用贪婪算法的思路,把start赋值为当前元素是安全的,因为后面找到的比start大的元素一定也比当前元素大。如果当前元素比start大且比mid小,那么把mid赋值为当前元素是安全的,首先当前元素是比start大的,其次后面找到的比mid大的元素一定也比当前元素大。根据上述的算法,能保证mid一定是比start大的。如果当前元素比mid大,那我们就成功找到一个递增数列了。

遍历中会出现一种情形,就是mid出现在start的前面。例如[2,3,1,……]这个数组,一开始start是2,mid是3。遍历到1时,start就变为了1,这时1是在3后面出现的。但这样也不会影响算法的正确性,因为mid的存在隐含地表明了它前面存在一个比它小的元素。所以如果在后面找到比mid大的元素,无论start的位置在哪,依然表面存在递增数列。如果后面找到比start大比mid小的元素,就可以把mid赋值为那个元素(同样是贪婪算法的思路),这时mid又跑到start的后面去了。

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        if(nums.size()<3) return false;
        int start = INT_MAX, mid = INT_MAX;
        
        for(int i=0; i<nums.size(); i++) {
            if(nums[i]<=start) start=nums[i];
            else if(nums[i]<=mid) mid=nums[i];
            else return true;
        }
        return false;
    }
};

© 著作权归作者所有

共有 人打赏支持
上一篇: 72. Edit Distance
下一篇: 57. Insert Interval
cofama
粉丝 0
博文 24
码字总数 19162
作品 0
广州
程序员
私信 提问
334_Increasing_Triplet_Subsequence

Increasing Triplet Subsequence Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Formally the function should: Return true......

大培哥
2016/04/15
233
0
判断是否有三个递增子序列 Increasing Triplet Subsequence

问题: Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Formally the function should: Return true if there exists i, j, k......

叶枫啦啦
2017/12/25
0
0
674. Longest Continuous Increasing Subsequence。

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray). Example 1: Input: [1,3,5,4,7] Output: 3 Explanation: The longest co......

Leafage_M
2018/01/09
0
0
Leetcode 674. Longest Continuous Increasing Subsequence

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Reference https://leetcode.com/problems/longest-continuous-increasing-subsequence/description/......

SnailTyan
2018/10/25
0
0
[LeetCode]Longest Continuous Increasing Subsequence 最长连续增长序列

链接:https://leetcode.com/problems/longest-continuous-increasing-subsequence/description/ 难度:Easy 题目:674. Longest Continuous Increasing Subsequence Given an unsorted arra......

繁著
2017/12/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Linux iptables之mangle表使用案例

mangle表的用途 mangle表的主要功能是根据规则修改数据包的一些标志位,以便其他规则或程序可以利用这种标志对数据包进行过滤或策略路由。 mangel表使用示例 示例1-策略路由1 内网的客户机通...

月下狼
36分钟前
2
0
OSChina 周日乱弹 —— 兼职我想去学学布偶戏

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @clouddyy : 《火炎 - 女王蜂》 《火炎 - 女王蜂》 手机党少年们想听歌,请使劲儿戳(这里) @小鱼丁 :还在睡觉突然接到一个小哥哥电话“x...

小小编辑
49分钟前
46
3
租房软件隐私保护如同虚设

近日,苏州市民赵先生向江苏新闻广播新闻热线025-84658888反映,他在“安居客”手机应用软件上浏览二手房信息,并且使用该软件自动生成的虚拟号码向当地一家中介公司进行咨询。可电话刚挂不久...

linux-tao
今天
3
0
分布式项目(五)iot-pgsql

书接上回,在Mapping server中,我们已经把数据都整理好了,现在利用postgresql存储历史数据。 iot-pgsql 构建iot-pgsql模块,这里我们写数据库为了性能考虑不在使用mybatis,换成spring jd...

lelinked
今天
6
0
一文分析java基础面试题中易出错考点

前言 这篇文章主要针对的是笔试题中出现的通过查看代码执行结果选择正确答案题材。 正式进入题目内容: 1、(单选题)下面代码的输出结果是什么? public class Base { private Strin...

一看就喷亏的小猿
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部