阅读 39

LeetCode递增的三元子序列

给定一个未排序的数组,判断这个数组中是否存在长度为 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

来源:力扣(LeetCode) 链接:leetcode-cn.com/problems/in…

解题思路

  1. 就是查询数组中有没有3个依次增加的数。
  2. 定义两个最大数
  3. 循环查询,首先判断是不是最小的值,maxOne在最前面判断,肯定是最小的,maxTwo就是第二大的,其他的就是最大的,没有就返回false。
public boolean increasingTriplet(int[] nums) {
    int maxOne = Integer.MAX_VALUE;
    int maxTwo = Integer.MAX_VALUE;

    for (int n : nums) {
        if(n<=maxOne) {
            maxOne = n;
        } else if (n<=maxTwo) {
            maxTwo = n;
        } else {
            return true;
        }
    }
    return false;
}
复制代码
关注下面的标签,发现更多相似文章
评论