Java version


  • 0
    W
    public class Solution {
    public boolean find132pattern(int[] nums) {
        if(nums.length < 3){
            return false;
        }
        int i = 0; 
        int j = 0;
        int k = 0;
        int n = nums.length;
        //If we think the unsorted array is like a curve function, where lots of local minimum and local maxmium points exist
        //So we need to find the local minimum, and local maximum first, and then we can find if there is a third point meets 132 pattern
        while(i < n){
            while(i + 1 < n && nums[i + 1] < nums[i]){
                i++;
            }
            int min_local = nums[i];//obtain local minimum
            if( i >= n - 2){
                return false;
            }
            j = i + 1;
            while(j + 1 < n && nums[j + 1] > nums[j]){
                j++;
            }
            if(j >= n - 1){
                return false;
            }
            int max_local = nums[j];//obtain local maximum
            k = j + 1;
            while(k < n){
                if(nums[k] > min_local && nums[k] < max_local){
                    return true;
                }
                k++;
            }
            i = j + 1;
        }
        return false;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.