[LeetCode] 334. Increasing Triplet Subsequence 递增三元子序列
2023-09-27 14:28:37 时间
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
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.
Example 1:
Input: [1,2,3,4,5]
Output: true
Example 2:
Input: [5,4,3,2,1]
Output: false
给一个非排序的数组,判断是否存在一个长度为3的递增子序列。 要求:T: O(n) S: O(1)
解法:由于时间和空间复杂度的要求,不能用排序或者DP的方法。遍历数组,用两个变量分别记录当前的最小值和第二小的值,如果发现一个比这两个都大的数,则组成了一个长度为3的子序列,返回True。如果遍历结束,没找到返回False。
Java:
public boolean increasingTriplet(int[] nums) { // start with two largest values, as soon as we find a number bigger than both, while both have been updated, return true. int small = Integer.MAX_VALUE, big = Integer.MAX_VALUE; for (int n : nums) { if (n <= small) { small = n; } // update small if n is smaller than both else if (n <= big) { big = n; } // update big only if greater than small but smaller than big else return true; // return if you find a number bigger than both } return false; }
Python:
def increasingTriplet(nums): first = second = float('inf') for n in nums: if n <= first: first = n elif n <= second: second = n else: return True return False
C++:
bool increasingTriplet(vector<int>& nums) { int c1 = INT_MAX, c2 = INT_MAX; for (int x : nums) { if (x <= c1) { c1 = x; // c1 is min seen so far (it's a candidate for 1st element) } else if (x <= c2) { // here when x > c1, i.e. x might be either c2 or c3 c2 = x; // x is better than the current c2, store it } else { // here when we have/had c1 < c2 already and x > c2 return true; // the increasing subsequence of 3 elements exists } } return false; }
All LeetCode Questions List 题目汇总
相关文章
- 【LeetCode】从前序与中序遍历序列构造二叉树 [M](二叉树重构)
- 【LeetCode】不同的子序列 [H](动态规划)
- [LeetCode]Subsets II生成组合序列
- LeetCode_滑动窗口_哈希表_中等_187. 重复的DNA序列
- LeetCode_二叉树_中等_106.从中序与后序遍历序列构造二叉树
- LeetCode·每日一题·801.使序列递增的最小交换次数·动态规划
- LeetCode·376.摆动序列·贪心·动态规划
- 「LeetCode」24. 两两交换链表中的节点
- LeetCode-LCP 18. 早餐组合(Goland实现)
- LeetCode-38. 外观数列(Goland实现)
- [LeetCode] 556. Next Greater Element III 下一个较大的元素 III
- [LeetCode] 549. Binary Tree Longest Consecutive Sequence II 二叉树最长连续序列之 II
- [LeetCode] 283. Move Zeroes 移动零
- leetcode 844 比较含退格的字符串
- leetcode 516 最长回文子序列
- leetcode 115 不同的子序列