程序设计－递增子序列easy版（Java）

分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程https://www.captainai.net/troubleshooterpackage live.every.day.bytedance; import org.junit.jupiter.api.Test; import static org.junit.jupiter.api.Assertions.assertTrue; /** * 【中等】递增子序列easy版 * * 题目描述 * 判断一个无序数组中是否存在长度为3的递增子序列不要求连续如果存在输出true否则输出false不含引号。 * 要求满足O(n)的时间复杂度和O(1)的空间复杂度。 * * 示例1 * 输入5 12 8 36 9 20 * 输出true * * author LiveEveryDay */ public class IncrementSubsequenceTest { Test public void testIncrementSubsequence() { int[] nums {5, 12, 8, 36, 9, 20}; assertTrue(IncrementSubsequence.exists(nums)); } }package live.every.day.bytedance; /** * 【中等】递增子序列easy版 * * 题目描述 * 判断一个无序数组中是否存在长度为3的递增子序列不要求连续如果存在输出true否则输出false不含引号。 * 要求满足O(n)的时间复杂度和O(1)的空间复杂度。 * * 示例1 * 输入5 12 8 36 9 20 * 输出true * * ---------------- * * 这是一个经典的算法问题目标是找到数组中是否存在三个元素下标 i j k使得 arr[i] arr[j] arr[k]。 * 为了满足 O(n) 的时间复杂度和 O(1) 的空间复杂度我们使用贪心算法的思想。我们维护两个变量 small 和 mid分别表示 * 当前找到的递增子序列中的第一个最小值和第二个中间值。 * * 算法思路 * 1. 初始化 small 和 mid 为无穷大或者大于数组中可能出现的最大值。 * 2. 遍历数组中的每一个数字 num * 如果 num 小于等于 small说明我们找到了一个更小的起点更新 small num。 * 否则如果 num 小于等于 mid说明我们找到了一个比 small 大但是比当前 mid 小或等于的数这能让我们更容 * 易找到第三个数所以更新 mid num。 * 否则即 num 大于 small 且 num 大于 mid说明我们找到了一个比前两个数都大的数即找到了长度为3的递增子序 * 列直接返回 true。 * 3. 如果遍历结束都没有返回 true则说明不存在长度为3的递增子序列返回 false。 * * author LiveEveryDay */ public class IncrementSubsequence { public static boolean exists(int[] nums) { // 初始化small和mid为整型最大值 int small Integer.MAX_VALUE; int mid Integer.MAX_VALUE; for (int num : nums) { if (num small) { // 如果当前数比最小值还小或相等更新最小值 small num; } else if (num mid) { // 如果当前数比最小值大但比中间值小或相等更新中间值 mid num; } else { // 如果当前数比最小值和中间值都大说明找到了长度为3的递增子序列 return true; } } // 遍历结束仍未找到返回false return false; } }