LeetCode - 334 - 递增的三元子序列 - Java - 细喔

文章目录

题目

题目解析

题目大意： 给我们一个数，让我们去判断 这个 数组中 从左往右 是否有 有三个元素 num[ i ]、num[ j ]、num[ k ]满足 num[ i ] < num[ j ] < num[ k ] ------递增关系。
有，返回true。
无，则返回false、

解题思维一： 双向遍历

直白来说 ：就是一个循环 正序（从左往右）遍历数组，另一个 逆序（从右往左）遍历数组，
为什么要这样遍历呢？，因为我们想通过这两次遍历确定 数组nums 中的最大值 和 最小值。因此，我们为此创建两个数组 leftMIn（记录这个数组中“最小值/num[i]”，不包括第一个元素。），rightMax（记录这个数组中“最大值/num[k]”，不包括最后一个袁术）。
最后，再正序遍历一次链表，用 num[ j ]去比较 num[ i ] 和 num[ k ]。

代码如下：

classSolution{publicbooleanincreasingTriplet(int[] nums){int n = nums.length;if(n <3){// 该数组 容量至少为 3 returnfalse;}int[] leftMin =newint[n];// 记录 “最小值”
        leftMin[0]= nums[0];// 第一个元素作为参考元素for(int i =1;i < n;i++){// 记录 从下标0到 i 下标，目前为止的最小值，将其存入 leftMin[i]
            leftMin[i]= Math.min(leftMin[i-1],nums[i]);}int[] rightMax =newint[n];// 记录 “最大值”
        rightMax[n-1]= nums[n-1];// 最后一个元素作为参考元素for(int k = n -2;k>=0;k--){//记录 从下标 n-1 到 k 下标，目前为止的最大值。将其存入 rightMax[k]
            rightMax[k]= Math.max(rightMax[k+1],nums[k]);}for(int j =1;j < n-1;j++){// num[j]  去比较 "num[i] == leftMin[j-1]" 和 "num[k] == rightMax[j+1]"if(nums[j]> leftMin[j-1]&& nums[j]< rightMax[j+1]){returntrue;// 满足 num[i] < num[j] < num[k]条件，返回 true}}returnfalse;// 没有满足条件的 num[j]，意味着递增三原子不存在。}}

代码细节

解题思维二： 贪心

这种思维 与上面不同是：我们不需要去过多的遍历数组，

思维是这样的： 将第一个元素 看作 num[0], 记为 i， 接着，循环遍历数组nums ：如果遇到 比 i 大的数据，就将其设置为 num [ 此时循环的变量k] 记为 j，或者，遇到 比 i 小的，就将 i 的 更新为 num [ 此时循环变量k ]。
然后接着遍历（可能过程中 i 和 j 的值，其值在不断更新），如果 num[k] > j 说明三元子序列存在，又或者遍历完整个程序，都没有找到 满足条件值值，也就是循环正常结束时，返回 false，表示 三元子序列不存在！

代码如下

classSolution{publicbooleanincreasingTriplet(int[] nums){int n = nums.length;if(n <3){// 该数组 容量至少为 3 returnfalse;}// i 为 三元子序列中最小值int i = nums[0];// j 为 三元子序列中 中间值int j = Integer.MAX_VALUE;//防止与 i 冲突，初始化为整形最大值// 循环数组，寻找 大于 j 的 num[k],三元子序列中的最大值，（期间：i 与 j 的值，始终在更新，确保 i 最小，j其次）for(int k =1;k < n; k++){if(nums[k]> j){// 第一次，肯定是不满足。正好用来 更新 i 或者 j 的值，下一次就不移动了哟returntrue;}elseif(nums[k]> i){// 比 i 值大，更新 j 值，
                j = nums[k];}else{// 比 i 小，更新 i 值。
                i = nums[k];}}returnfalse;}}