Formally the function should:
Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Your algorithm should run in O(n) time complexity and O(1) space complexity.
Examples:
Given [1, 2, 3, 4, 5],
return true.
Given [5, 4, 3, 2, 1],
return false.
Credits:
Special thanks to @DjangoUnchained for adding this problem and creating all test cases.
public class Solution { public boolean increasingTriplet(int[] nums) { int small = Integer.MAX_VALUE, big = Integer.MAX_VALUE; for (int n : nums) { if (n <= small) small = n; else if (n <= big) big = n; else return true; } return false; } }
public class Solution { public boolean increasingTriplet(int[] nums) { int min = Integer.MAX_VALUE; int mid = Integer.MAX_VALUE; int altMin = Integer.MAX_VALUE; for(int i =0; i<nums.length; ++i) { if(nums[i]<min) { if(mid == Integer.MAX_VALUE) //If mid val hasn‘t been set min = nums[i]; else if(altMin < nums[i]) //If in (alterMin, Min), reset Min & Mid { min = altMin; mid = nums[i]; altMin = Integer.MAX_VALUE; } else if(nums[i] < altMin) //update the alternative min, which is less than min. altMin = nums[i]; } else if(nums[i]<mid) { if(nums[i] > altMin) //If in (alterMin, Mid), reset Min & Mid { min = altMin; mid = nums[i]; altMin = Integer.MAX_VALUE; } else if(nums[i] > min) mid = nums[i]; // Reset mid if alterMin is not set. } else if(nums[i]>mid) { return true; } } return false; } }
334. Increasing Triplet Subsequence
原文：http://www.cnblogs.com/neweracoding/p/5556041.html