• 售前

  • 售后

热门帖子
入门百科

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

[复制链接]
干将发硎鞘 显示全部楼层 发表于 2022-1-13 13:53:32 |阅读模式 打印 上一主题 下一主题
文章目录



题目




题目解析

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

  

解题思维一: 双向遍历

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

  

代码如下:

  1. class Solution {
  2.     public boolean increasingTriplet(int[] nums) {
  3.         int n = nums.length;
  4.         if(n < 3){// 该数组 容量至少为 3
  5.             return false;
  6.         }
  7.         int[] leftMin = new int[n];// 记录 “最小值”
  8.         leftMin[0] = nums[0];// 第一个元素作为参考元素
  9.         for(int i = 1;i < n;i++){// 记录 从下标0到 i 下标,目前为止的最小值,将其存入 leftMin[i]
  10.             leftMin[i] = Math.min(leftMin[i-1],nums[i]);
  11.         }
  12.         int[] rightMax = new int[n];// 记录 “最大值”
  13.         rightMax[n-1] = nums[n-1];// 最后一个元素作为参考元素
  14.         for(int k = n -2;k>=0;k--){//记录 从下标 n-1 到 k 下标,目前为止的最大值。将其存入 rightMax[k]
  15.             rightMax[k] = Math.max(rightMax[k+1],nums[k]);
  16.         }
  17.         for(int j = 1;j < n-1;j++){// num[j]  去比较 "num[i] == leftMin[j-1]" 和 "num[k] == rightMax[j+1]"
  18.             if(nums[j] > leftMin[j-1] && nums[j] < rightMax[j+1]){
  19.                 return true;// 满足 num[i] < num[j] < num[k]条件,返回 true
  20.             }
  21.         }
  22.         return false;// 没有满足条件的 num[j],意味着递增三原子不存在。
  23.     }
  24. }
复制代码



代码细节




解题思维二: 贪心

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

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

  

代码如下

  1. class Solution {
  2.     public boolean increasingTriplet(int[] nums) {
  3.         int n = nums.length;
  4.         if(n < 3){// 该数组 容量至少为 3
  5.             return false;
  6.         }
  7.         // i 为 三元子序列中最小值
  8.         int i = nums[0];
  9.         // j 为 三元子序列中 中间值
  10.         int j = Integer.MAX_VALUE;//防止与 i 冲突,初始化为整形最大值
  11.         // 循环数组,寻找 大于 j 的 num[k],三元子序列中的最大值,(期间:i 与 j 的值,始终在更新,确保 i 最小,j其次)
  12.         for(int k = 1;k < n; k++){
  13.             if(nums[k] > j){// 第一次,肯定是不满足。正好用来 更新 i 或者 j 的值,下一次就不移动了哟
  14.                 return true;
  15.             }else if(nums[k] > i){// 比 i 值大,更新 j 值,
  16.                 j = nums[k];
  17.             }else{// 比 i 小,更新 i 值。
  18.                 i = nums[k];
  19.             }
  20.         }
  21.         return false;
  22.     }
  23. }
复制代码


来源:https://blog.caogenba.net/DarkAndGrey/article/details/122459064
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作