题目大意：
递增的三元子序列
给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。
数学表达式如下:
- 如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1，
- 使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。
示例 1:
输入: [1,2,3,4,5] 输出: true
示例 2:
输入: [5,4,3,2,1] 输出: false
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=334
解题思路分析：
本题求长度为3的递增子序列，我们使用2个变量代表，遍历到当前位置时的最小数m1，和次小数m2。初始时m1和m2均为整数最大值。如果当前数小于m1，m1更新为当前数，如果当前数大于等于m1并且小于m2，将m2更新为当前数，此时，说明我们找到了2个递增数字。如果当前数大于m2，说明我们找到了3个递增数，返回true即可。
我在网上看了大部分文章，基本讲到这里就结束了，但如果不能充分理解本解法的实质，你可能会对上述逻辑产生质疑，我们来用一个极端的例子说明。比如数组：
int[] nums =[11, 12, 0, 13];
根据上面的逻辑我们手动执行一遍代码：
- index为0，当前数字是11，最小值是11
- index为1，当前数字是12，次小值是12
- 重点来了！index为2，当前数是0，我们更新最小值为0，次小值不变。最多的疑问会出现在这里，当前最小值是0，次小值是12，然而在原数组中0是在12后面出现的，此时0和12虽然是递增，由于顺序原因，它并非是子序列，这样做合理吗？答案是肯定的，至少对于本题来说是合理的。因为将最小值从11变为0，并不能改变12是次小数的事实，只不过在12之前比12小的不是0，而是11。更新最小值的目的是为了之后有可能更改次小值做准备而已（比如这样的数组：[11,12,0,1,2]）。本题这样做的原因是，题目只要求求出是否存在连续递增子序列，而没有要求列出具体的子序列内容，如果题目要求列出具体序列元素的话，这种解法显然行不通。
- index为3，当前数字为13，大于m2，返回true。
实现代码：
public boolean increasingTriplet(int[] nums) {
int m1 = Integer.MAX_VALUE;
int m2 = Integer.MAX_VALUE;
for (int a : nums) {
if (a <= m1) m1 = a;
else if (a <= m2) m2 = a;
else return true;
}
return false;
}本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Increasing Triplet Subsequence.
Memory Usage: 43.3 MB, less than 6.98% of Java online submissions for Increasing Triplet Subsequence.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-334-increasing-triplet-subsequence-解题思路分析/