Incremental ternary subsequence [greedy training]

Preface

Greed requires careful analysis + Clever thinking , Therefore, we need the accumulation of detailed thinking during daily practice + Breadth of knowledge , It is a good type of problem to investigate the ability of algorithm problem , And monotone stack /dp equally .

One 、 Increasing ternary subsequences

Two 、 Greedy practice

package everyday.greed;

//  Increasing ternary subsequences 
public class IncreasingTriplet {
    
    /* target： Front middle back , Whether there is an increasing sequence .  It is possible to record  */
    // 4 5 1 2 3
    // 4 5 1 8
    //  Violence to find feelings 
    public boolean increasingTriplet(int[] nums) {
    
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
    
            for (int j = i + 1; j < n - 1; j++) {
    
                if (nums[i] >= nums[j]) continue;
                for (int k = j + 1; k < n; k++) {
    
                    if (nums[j] >= nums[k]) continue;
                    return true;
                }
            }
        }
        return false;
    }

    /*  Small middle right , In the middle mid For reference point . If there is the smallest element on the left minLeft & minLeft < mid. The largest element on the right maxRight & maxRight > mid, There are such triples .  You can record the minimum left and maximum right in advance , Space for time . */
    public boolean increasingTriplet2(int[] nums) {
    
        int n = nums.length;
        int[] minLeft = new int[n];
        int[] maxRight = new int[n];
        //  Fill in the smallest element on the left .
        // bug1:1 << 31 yes Integer.MIN_VALUE;1 << 30 Not at all Integer.MAX_VALUE
        int min = 0x7FFFFFFF;
        // int min = -((1 << 31) + 1);
        for (int i = 0; i < n; i++) {
    
            minLeft[i] = min;
            min = Math.min(min, nums[i]);
        }
        int max = 1 << 31;
        for (int i = n - 1; i >= 0; i--) {
    
            maxRight[i] = max;
            max = Math.max(max, nums[i]);
        }
        //  Traverse nums, Make it nums[i] For the center , Determine whether there are qualified nodes on both sides .
        for (int i = 0; i < n; i++) if (nums[i] > minLeft[i] && maxRight[i] > nums[i]) return true;
        //  Such triples cannot be found .
        return false;
        /*  summary ： Why can't I think of this practice ？  First of all , The accumulation of algorithm knowledge is less , Too little knowledge .  second , Due to accumulation , still get Not to the key point of the problem .  Third , This multi-element relative problem , The reference point is too rigid , For example, if you come up, you can find Zuo first -> Find the center larger than the left -> Find the right greater than the middle .  If I decide first , Just find the left smaller than the middle  -> Think of this left as the minimum value of left ; Then find the right greater than the middle -> Think of this right as the maximum value of the right .  Thus, I think of using space for time , Record left -> The minimum value of right ; Right -> The maximum value of the left . */
    }

    /*  The above ideas , Give us ： The left side is the smallest , The right side is the largest .  To the left left  in mid  For reference , Look for right right,  If right > mid, Then find the legal triples ;  If right > left, The replacement mid = right, Let the smaller value be in .  If right < left, Then let right Become Zuo Xiao , Fix the left smallest , Isn't that right mid Need to change , After all mid The subscript of is less than right Of ！  Unwanted , The original left < mid The relationship still exists ,right displacement left, Just make sure that the following values can be replaced slowly mid, And then find the truth that meets the conditions right.  as long as left Position in , It saves what once existed left < mid Relationship , and left = right, It also keeps the current minimum value information on the left , In order to find . */
    public boolean increasingTriplet3(int[] nums) {
    
        int left = nums[0], mid = 0x7FFFFFFF;
        for (int i = 1; i < nums.length; i++) {
    
            int right = nums[i];
            if (right > mid) return true;
            if (right > left) mid = right;
            else left = right;
        }
        //  Not found 
        return false;
        /*  summary ： This greed , It really needs some analysis & understand & Sense & Only through training can you think .  So I want to learn algorithm knowledge & See the algorithm ideas there are many first 500 -> 1000 -> 2000 It's a question , There is still a long way , There's still a lot to learn , analysis & The ability to understand problems needs more training . */
    }
}

summary

1） Why can't I think of this practice ？
First of all , The accumulation of algorithm knowledge is less , Too little knowledge ;
second , Due to accumulation , still get Not to the key point of the problem ;
Third , This multi-element relative problem , The reference point is too rigid , For example, if you come up, you can find Zuo first -> Find the center larger than the left -> Find the right greater than the middle .

If I decide first , Just find the left smaller than the middle -> Think of this left as the minimum value of left ; Then find the right greater than the middle -> Think of this right as the maximum value of the right .

Thus, I think of using space for time , Record left -> The minimum value of right ; Right -> The maximum value of the left .2） Why can't such clever greed think of ？
It really needs some analysis & understand & Sense & Only through training can you think .
So I want to learn algorithm knowledge & See the algorithm ideas there are many first 500 -> 1000 -> 2000 It's a question , There is still a long way , There's still a lot to learn , analysis & The ability to understand problems needs more training .

reference

[1] LeetCode Increasing triples