我正在解决一个问题,内容如下:
Given an unsorted array return whether an increasing subsequence of length 3 exists in the array or not. Formally return true if there exists i, j, k such that:
arr[i]<arr[j]<arr[k] given 0 <= i < j < k <= n-1
这是我的代码:
public boolean increasingTriplet(int[] nums) {
if (nums.length < 3) return false;
for (int i = 0; i < nums.length-2; i++) {
if (nums[i] < nums[i+1]) {
if (nums[i+1] < nums[i+2]) return true;
}
}
return false;
}
我的代码在以下输入时失败:
[5,1,5,5,2,5,4]
显然我的代码应该针对这个序列返回 true,但我一生都无法弄清楚为什么,因为我没有看到任何长度为 3 的递增子序列。非常感谢任何帮助理解这个问题的帮助。
public boolean increasingTriplet(int[] nums) {
int first=Integer.MAX_VALUE;
int second=Integer.MAX_VALUE;
int third=Integer.MAX_VALUE;
for(int p=0; i<nums.length; p++){
if(nums[p]<=third){
third=nums[p];
}else{
if(nums[p]<=second){
first=third;
second=nums[p];
}else{
return true;
}
}
}
return false;
}
这段代码背后的整体思想是,如果我们找到了一对递增序列的值,那么只有当新对的第一个值小于旧对的第一个值时,我们才能用新的一对递增序列替换该对。新对的第二值小于旧对的第二值。同时,我们检查该数字是否大于完成序列的第二个数字(在这种情况下我们将返回
true
)。
代码开始比较从第三个到第二个的值,而不是从第一个到第二个,但想法与上面相同。
这是一种可能的解决方案:
public static boolean increasingTriplet(int[] nums) {
for (int i = 0; i < nums.length-2; ++i) {
for (int j = i+1; j < nums.length-1; ++j) {
if (nums[j] > nums[i]) {
for (int k = j+1; k < nums.length; ++k) {
if (nums[k] > nums[j]) {
return true;
}
}
}
}
}
return false;
}