【LeetCode】Increasing Triplet Subsequence(334)

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

1. Description


  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, ksuch that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < kn-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:


Given [1, 2, 3, 4, 5],

return true.

Given [5, 4, 3, 2, 1],

return false.

 

2. Answer 

 

  solution1 :

public class Solution {
    public boolean increasingTriplet(int[] nums) {
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (nums[j] > nums[i]) {
                    for (int k = j + 1; k < nums.length; k++) {
                        if (nums[k] > nums[j])
                            return true;
                    }
                }
            }
        }
        return false;
    }
}

solution2:

public class Solution {
    public boolean increasingTriplet(int[] nums) {
        int min = Integer.MAX_VALUE;
        int secondMin = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] <= min){
                min = nums[i];
            }
            else if (nums[i] <= secondMin){
                secondMin = nums[i];
            }
            else {
                return true;
            }
        }
        return false;
    }
} 

solution2 has a better time complexity, it is a better way.

目录
相关文章
Leetcode 516. Longest Palindromic Subsequence
找到一个字符串的最长回文子序列,这里注意回文子串和回文序列的区别。子序列不要求连续,子串(substring)是要求连续的。leetcode 5. Longest Palindromic Substring就是求连续子串的。
50 0
|
索引
LeetCode 392. Is Subsequence
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
104 0
LeetCode 392. Is Subsequence
LeetCode 376. Wiggle Subsequence
如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。
100 0
LeetCode 376. Wiggle Subsequence
|
算法
LeetCode 334. Increasing Triplet Subsequence
给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列。 数学表达式如下: 如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1, 使得 arr[i] < arr[j] < arr[k] ,返回 true ; 否则返回 false 。
94 0
LeetCode 334. Increasing Triplet Subsequence
|
存储
LeetCode 329. Longest Increasing Path in a Matrix
给定一个整数矩阵,找出最长递增路径的长度。 对于每个单元格,你可以往上,下,左,右四个方向移动。 你不能在对角线方向上移动或移动到边界外(即不允许环绕)。
75 0
LeetCode 329. Longest Increasing Path in a Matrix
|
算法
LeetCode 300. Longest Increasing Subsequence
给定一个无序的整数数组,找到其中最长上升子序列的长度。
54 0
LeetCode 300. Longest Increasing Subsequence
LeetCode contest 183 5376. 非递增顺序的最小子序列 Minimum Subsequence in Non-Increasing Order
LeetCode contest 183 5376. 非递增顺序的最小子序列 Minimum Subsequence in Non-Increasing Order
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
58 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
120 2