Leetcode skimming -- incremental ternary subsequence 334 medium

Discussion and source code of increasing ternary subsequence
     The title of the increasing ternary subsequence is shown in the figure below , This question belongs to greedy class and array type , It mainly investigates the use of search methods and the understanding of array structure . The title of this article, the author thought 2 Methods , They are two-way traversal method and binary search method , The bidirectional traversal method uses Java Compiling , The binary search method uses Python Compiling , Of course, this may not be the optimal solution , I also hope you guys can give a faster algorithm .

     I think this problem can be solved by using the idea of two-way traversal , First calculate the length of the array , If the length of the array is less than 3, Then return directly False Result . Then initialize an integer array , Make the first element of the new array equal to the first element of the original array . Start looping through the original array , Assign the minimum value of the current element of the original array and the previous element of the new array to the current element of the new array . Then initialize an integer array , Make the last element of the new array equal to the last element of the original array . Loop through the original array from the back to the front , Assign the maximum value of the current element of the original array and the previous element of the new array to the current element of the new array . Finally, traverse three arrays , When the condition is met, the current element is larger than the previous element of the left array and smaller than the next element of the right array True Result , Otherwise, it will return at the end of traversal False result . Then according to this idea, our Java The code is as follows ：

# Fire breathing dragon and water arrow turtle 
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int numLen = nums.length;
        if (numLen < 3) {
            return false;
        }
        int[] leftMin = new int[numLen];
        leftMin[0] = nums[0];
        for (int ir = 1; ir < numLen; ir++) {
            leftMin[ir] = Math.min(leftMin[ir - 1], nums[ir]);
        }
        int[] rightMax = new int[numLen];
        rightMax[numLen - 1] = nums[numLen - 1];
        for (int ir = numLen - 2; ir >= 0; ir--) {
            rightMax[ir] = Math.max(rightMax[ir + 1], nums[ir]);
        }
        for (int ir = 1; ir < numLen - 1; ir++) {
            if (nums[ir] > leftMin[ir - 1] && nums[ir] < rightMax[ir + 1]) {
                return true;
            }
        }
        return false;
    }
}

     obviously , We can see that the effect of the two-way search method is ok , At the same time, it can also be solved by binary search . Initialize first , Assign the minimum value to two user-defined variables, the minimum value variable and the intermediate value variable , Then start traversing the array , If the current element is less than or equal to the minimum , Assign the current element to the minimum value . Otherwise, if the current element is less than or equal to the intermediate value , Assign the current element to the intermediate value , Otherwise, go straight back to True Result . If the traversal has not returned to the end , Go straight back False Result . So according to this idea, we can solve , Here is Python Code ：

# Fire breathing dragon and water arrow turtle 
class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        smallNum = inf
        middleNum = inf
        for ij in nums:
            if(ij <= smallNum):
                smallNum = ij
            elif(ij <= middleNum):
                middleNum = ij
            else:
                return True
        return False

     As a result Java The efficiency of the version of the two-way search method is relatively poor , and Python The speed of the binary search method of version is ok , But there should be more ways to further speed up , I hope friends can give me more advice , Thank you very much .