LeetCode_贪心算法_中等_334. 递增的三元子序列
2023-09-27 14:25:46 时间
1.题目
给你一个整数数组 nums ,判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ,使得 nums[i] < nums[j] < nums[k] ,返回 true ;否则,返回 false 。
示例 1:
输入:nums = [1,2,3,4,5]
输出:true
解释:任何 i < j < k 的三元组都满足题意
示例 2:
输入:nums = [5,4,3,2,1]
输出:false
解释:不存在满足题意的三元组
示例 3:
输入:nums = [2,1,5,0,4,6]
输出:true
解释:三元组 (3, 4, 5) 满足题意,因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
提示:
1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1
进阶:你能实现时间复杂度为 O(n) ,空间复杂度为 O(1) 的解决方案吗?
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/increasing-triplet-subsequence
2.思路
(1)暴力穷举法
暴力穷举法比较容易想到,使用三层 for 循环遍历所有可能的三元组下标 (i, j, k) ,并逐个进行判断即可。但显然该方法的时间复杂度较高,在 LeetCode 中提交时会显示“超出时间限制”的提示!
(2)贪心算法
思路参考本题官方题解。
3.代码实现(Java)
//思路1————暴力穷举法
class Solution {
public boolean increasingTriplet(int[] nums) {
boolean flag = false;
int length = nums.length;
for (int i = 0; i < length - 2; i++) {
for (int j = i + 1; j < length - 1; j++) {
if (nums[i] < nums[j]) {
for (int k = j + 1; k < length; k++) {
if (nums[j] < nums[k]) {
return true;
}
}
}
}
}
return flag;
}
}
//思路2————贪心算法
public boolean increasingTriplet(int[] nums) {
/*
本题贪心算法的主要思想:
为了找到递增的三元子序列,first 和 second 应该尽可能地小,此时找到递增的三元子序列的可能性更大
*/
int length = nums.length;
int first = nums[0];
int second = Integer.MAX_VALUE;
//下面在遍历的过程中,始终保证 first < second
for (int i = 1; i < length; i++) {
//遍历到的每一个 num 可以看作要找的第 3 个数
int num = nums[i];
if (num > second) {
// first < second < num,找到了符合条件的三元组,直接返回 true
return true;
} else if (num > first) {
// first < num <= second,将 num 赋值给 second,尽可能保证 first 和 second 之间的差距较小,以便于寻找第 3 个数
second = num;
} else {
// num <= first < second,将 first 更新为 num
first = num;
}
}
return false;
}
相关文章
- 【LeetCode】最长递增子序列 [M](动态规划)
- 【LeetCode-面试算法经典-Java实现】【054-Spiral Matrix(螺旋矩阵)】
- LeetCode_哈希表_简单_594.最长和谐子序列
- LeetCode_动态规划_困难_552.学生出勤记录 II
- LeetCode_竖式计算_中等_166.分数到小数
- LeetCode_二分搜索_中等_240.搜索二维矩阵 II
- LeetCode_二叉树_中等_105.从前序与中序遍历序列构造二叉树
- LeetCode_动态规划_中等_198.打家劫舍
- LeetCode_动态规划_二分搜索_耐心排序_中等_300.最长递增子序列
- LeetCode_排序_快速选择_中等_215.数组中的第K个最大元素
- leetcode 152 乘积最大子序列
- LeetCode·106.从中序与后序遍历序列构造二叉树·递归
- LeetCode·491.递增子序列·递归+回溯+剪枝
- LeetCode·每日一题·剑指 Offer || 115.重建序列·拓扑排序
- LeetCode·124.二叉树中的最大路径和·递归
- LeetCode-164. 最大间距(Java实现)
- [LeetCode] 659. Split Array into Consecutive Subsequences 将数组分割成连续子序列
- [LeetCode] 227. Basic Calculator II 基本计算器 II
- leetcode 115 不同的子序列
- leetcode 105 从前序与中序遍历序列构造二叉树
- leetcode 376摆动序列