We can easily find that whether there exists a triple of indices (i,j,k) such that i<j<k and nums[i]<nums[j]<nums[k] only traversing the array once, but the problem is how to make our mind into algorithms.
Brute Force
It’s easy to use Brute Force way to solve this problem, but the time complexity is O(n3), it will TLE, so we need to find a better way.
int len = nums.length; for (int i = 0; i < len; i++) { for (int j = i + 1; j < len; j++) { for (int k = j + 1; k < len; k++) { if (nums[i] < nums[j] && nums[j] < nums[k]) { returntrue; } } } }
returnfalse; }
Analysis
Time Complexity: O(n3)
Space Complexity: O(1)
Dynamic Programming
We can also use DP method to solve it.
Let dp[i] represents the maximum length of a increasing sequence.
publicbooleanincreasingTriplet(int[] nums){ int len = nums.length;
int[] dp = newint[len]; Arrays.fill(dp, 1);
for (int i = 0; i < len; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = dp[j] + 1; }
if (dp[i] >= 3) { returntrue; } } }
returnfalse; }
Analysis
Time Complexity: O(n2)
Space Complexity: O(n)
Two Pointers
When traversing the array nums[j], 0<j<n−1, if there is an element on the left of nums[i]<nums[j], 0≤i<j, and an element on the right of nums[k], j<k<len.
Therefore, we can maintain the minimum value on the left and the maximum value on the right of each element in the array.