Massive Algorithms: LeetCode 456

LeetCode 456 - 132 Pattern

http://bookshadow.com/weblog/2016/11/13/leetcode-132-pattern/

Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note: n will be less than 15,000.

Example 1:

Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: [3, 1, 4, 2]

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: [-1, 3, 2, 0]

Output: True

Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

BST（Binary Search Tree 二叉查找树）

首先利用TreeMap（采用红黑树实现）统计nums中所有元素的个数，记为tm

变量min记录访问过元素的最小值

遍历数组nums，记当前数字为num

  将num在tm中的计数-1，计数为0时将num从tm中删去

  如果num < min，则更新min值为num

  否则，若tm中大于min的最小元素<num，则返回true

遍历结束，返回false

https://leetcode.com/problems/132-pattern/discuss/94107/O(n*logn)-treeMap-%2B-explanation

The idea is to try to fix the nums[i] as a maximum value. The next step is to find minimum from our prefix. Then try to find if there exists the value in suffix which is greater than minimum and less than nums[i]. To find that value fast we can use tree map to count each number's occurrences and use it's lower() function.

public boolean find132pattern(int[] nums) { TreeMap<Integer, Integer> tm = new TreeMap<>(); for (int num : nums) { tm.put(num, tm.getOrDefault(num, 0) + 1); } int min = Integer.MAX_VALUE; for (int num : nums) { int cnt = tm.get(num); if (cnt > 1) { tm.put(num, cnt - 1); } else { tm.remove(num); } if (num <= min) { min = num; } else { Integer target = tm.higherKey(min); if (target != null && target < num) { return true; } } } return false; }
X.
https://leetcode.com/articles/132-pattern/#approach-5-using-binary-search-accepted

    public boolean find132pattern(int[] nums) {
        if (nums.length < 3)
            return false;
        int[] min = new int[nums.length];
        min[0] = nums[0];
        for (int i = 1; i < nums.length; i++)
            min[i] = Math.min(min[i - 1], nums[i]);
        for (int j = nums.length - 1, k = nums.length; j >= 0; j--) {
            if (nums[j] > min[j]) {
                k = Arrays.binarySearch(nums, k, nums.length, min[j] + 1);
                if (k < 0)
                    k = -1 - k;
                if (k < nums.length && nums[k] < nums[j])
                    return true;
                nums[--k] = nums[j];
            }
        }
        return false;
    }

X. Monotonic Stack

public boolean find132pattern(int[] nums) {

if (nums.length < 3)

return false;

Stack<Integer> stack = new Stack<>();

int[] min = new int[nums.length];

min[0] = nums[0];

for (int i = 1; i < nums.length; i++)

min[i] = Math.min(min[i - 1], nums[i]);

for (int j = nums.length - 1; j >= 0; j--) {

if (nums[j] > min[j]) {

while (!stack.isEmpty() && stack.peek() <= min[j])

stack.pop();

if (!stack.isEmpty() && stack.peek() < nums[j])

return true;

stack.push(nums[j]);

}

return false;

}

http://hehejun.blogspot.com/2017/09/leetcode132-pattern.html
假设我们从左向右遍历，每找到一个符合条件的pair(a, b)，a < b，之后我们如果碰到在(a, b)范围内的数就说明我们找到了符合条件的pattern。但问题是我们可能有多个这样的pair，这样符合要求的区间也可能有多个，这样让我们并不好判断当前数是否符合条件。

如果换一种思维，从右向左依次遍历的话，我们可以发现可以简单很多，对于处在i位置的数nums[i]，如果存在j > i的数满足nums[i] > nums[j]，我们只需要判断在[i + 1, len - 1]区间里，小于nums[i]的最大数c是什么即可，以后如果我们遇到小于c的数就说明我们找到了这样一个pattern。那么我们将这道题转化为对于nums[i]我们如何求出[i + 1, len - 1]小于nums[i]的最大数c。很显然，如果用我们熟知的数据结构，BST可以帮我们做到这一点，时间复杂度为O(n * log n)。但是这里还是依然有重复的计算，假设我们在遍历到b的时候找到了c，我们遇到了一个比b更大的数x，那么我们需要去更新c，因为x的存在可能可以让c变得更大，这样我们找132pattern的第一个数的限制条件会更宽松。那么这一次更新的过程，我们完全就不需要考虑之前在b已经排除的数字了。如果我们用stack维护一个从右向左的递减序列，每当我们碰到了比栈顶更大的数curr，我们pop直到我们得到比curr小的最大值，那么我们就得到了c，同时排除了所有我们之后不需要考虑的数，我们继续插入curr继续之前的步骤，直到我们找到pattern或者发现不存在pattern。这样的话，每个数最多只会在栈上进出一次，时间复杂度O(n)，空间复杂度O(n)

值得一提的是，维护单调序列来避免重复计算的思路在很多题当中都有出现。比如: Largest Rectangle in Histogram, Sliding Window Maximum
https://blog.csdn.net/magicbean2/article/details/78531200
这道题目暴力法当然就是三重循环了，时间复杂度O(n^3)，肯定过不了大数据测试。我看到最巧妙的代码仅仅需要遍历一遍，所以时间复杂度是O(n)。下面我们仔细分析。

假设我们要找到一个123序列，即s1 < s2 < s3，那么我们只需要依次找到s3，s2和s1即可。现在我们需要找到一个132序列，其中s1 < s3 < s2，我们就需要交换一下搜索顺序：首先找到s2，然后再找s3，最后找s1。更准确地讲，我们在搜索s1的过程中，记录下合法(s2 > s3)对子中s3的最大值。一旦我们在左侧发现一个小于最大s3的s1，则就可以返回了，这是因为s1 < s3可以推导出s1 < s2。

我们既可以从左到右扫描，也可以从右到左扫描，但是从右到左扫描仅仅需要扫描一遍。思路是：从右到左开始搜索合法的(s2, s3)对子。我们只需要记录下来最大的s3，而使用栈这种数据结构可以高效地达到这个目的。如果在某个数的左侧存在一大大于它的数，它就是s3的合法候选者。

由于我们是从右到左扫描的，所以我们可以容易地维护合法(s2, s3)对子中最大的s3的值。因此，每次我们比较nums[i]与区间nums[i + 1]...nums[n-1]的最大s3候选者，我们就可以问一个问题：是否存在以s1 = nums[i]为开头的132序列？因此，如果函数返回false，那么一定就没有132序列。这就证明了算法的正确性。

实现步骤如下：

1）定义一个栈，每次当我们存储一个新数的时候，我们首先弹出里面所有比它小的数字。而弹出的这些数就会成为s3的有效候选者。

2）我们维护s3的最大候选者（它一定是从栈中最后一个被弹出的数字）；

3）一旦我们遇到一个比s3小的数，就说明我们找到了合法的序列s1 < s3。由于s2 > s3，所以一定可以推导出s1 < s2。

运行时间分析：由于每个数字最多入栈和出栈各一次，所以整个时间复杂度是O(n)。

对于序列[9, 11, 8, 9, 10, 7, 9]，整个代码的运行过程如下：

i = 6, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 9, S3 candidate = None, Stack = Empty
i = 5, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 7, S3 candidate = None, Stack = [9]
i = 4, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 10, S3 candidate = None, Stack = [9,7]
i = 3, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 9, S3 candidate = 9, Stack = [10]
i = 2, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 8, S3 candidate = 9, Stack = [10,9] We have 8<9, sequence (8,10,9) found!

https://discuss.leetcode.com/topic/67881/single-pass-c-o-n-space-and-time-solution-8-lines-with-detailed-explanation

We want to search for a sub sequence (s1,s2,s3)

INTUITION: The problem would be simple if we want to find sequence with s1 > s2 > s3, we just need to find s1, followed by s2 and s3. Now if we want to find a 132 sequence, we need to switch up the order of searching. we want to first find s2, followed by s3, then s1.

IDEA: We can start from either side but I think starting from the end allow us to finish in a single pass. The idea is to start from end and search for a candidate for s2 and s3. A number becomes a candidate for s3 if there is any number on the left (s2) that is bigger than it.

DETECTION: Keep track of the largest candidate of s3 and once we encounter any number smaller than s3, we know we found a valid sequence since s1 < s3 implies s1 < s2.

IMPLEMENTATION:

Have a stack, each time we store a new number, we first pop out all numbers that are smaller than that number. The numbers that are popped out becomes candidate for s3.
We keep track of the maximum of such s3.
Once we encounter any number smaller than s3, we know we found a valid sequence since s1 < s3 implies s1 < s2.

RUNTIME: Each item is pushed and popped once at most, the time complexity is therefore O(n).

    bool find132pattern(vector<int>& nums) {
        int s3 = INT_MIN;
        stack<int> st;
        for( int i = nums.size()-1; i >= 0; i -- ){
            if( nums[i] < s3 ) return true;
            else while( !st.empty() && nums[i] > st.top() ){ 
              s3 = max( s3, st.top() ); st.pop(); 
            }
            st.push(nums[i]);
        }
        return false;
    }

public boolean find132pattern(int[] nums) {
    Stack<Integer> stack = new Stack<>();
    for (int i = nums.length - 1, two = Integer.MIN_VALUE; i >= 0; stack.push(nums[i--]))
        if (nums[i] < two) return true;
        else for (; !stack.empty() && nums[i] > stack.peek(); two = Math.max(two, stack.pop()));
    return false;
}

思路是我们维护一个栈和一个变量third，其中third就是第三个数字，也是pattern 132中的2，栈里面按顺序放所有大于third的数字，也是pattern 132中的3，那么我们在遍历的时候，如果当前数字小于third，即pattern 132中的1找到了，我们直接返回true即可，因为已经找到了，注意我们应该从后往前遍历数组。如果当前数字大于栈顶元素，那么我们按顺序将栈顶数字取出，赋值给third，然后将该数字压入栈，这样保证了栈里的元素仍然都是大于third的，我们想要的顺序依旧存在，进一步来说，栈里存放的都是可以维持second > third的second值，其中的任何一个值都是大于当前的third值，如果有更大的值进来，那就等于形成了一个更优的second > third的这样一个组合，并且这时弹出的third值比以前的third值更大，为什么要保证third值更大，因为这样才可以更容易的满足当前的值first比third值小这个条件

X.
https://discuss.leetcode.com/topic/67615/share-my-easy-and-simple-solution
the worst case time complexity for this one is O(n^2) when the array is in ascending order, right?

Idea: Find peak and bottom

For every [bottom, peak], find if there is one number bottom<number<peak.

    public boolean find132pattern(int[] nums) {
        if(nums.length<3) return false;
        Integer low = null, high = null;
        int start = 0, end = 0;
        while(start<nums.length-1){
            while(start<nums.length-1 && nums[start]>=nums[start+1]) start++;
            // start is lowest now
            int m = start+1; //no need to use m - use end instead
            while(m<nums.length-1 && nums[m]<=nums[m+1]) m++;
            // m is highest now
            int j = m+1;
            while(j<nums.length){
                if(nums[j]>nums[start] && nums[j]<nums[m]) return true;
                j++;
            }
            start = m+1;
        }
        return false;
    }

X.
https://discuss.leetcode.com/topic/67592/java-straightforward

public boolean find132pattern(int[] nums) {
        int len = nums.length;
        if(len < 3) return false;
        int[] max_cache = new int[len];
        int[] min_cache = new int[len];
        
        min_cache[0] = nums[0];
        for(int j = 1; j < len ; j++){
            min_cache[j] = Math.min(min_cache[j-1], nums[j]);
        }
        max_cache[len-1] = nums[len-1];
        for(int j = len-2; j >= 0; j--){
            max_cache[j] = Math.max(max_cache[j+1], nums[j]);
        }
        for(int i = 1; i < len-1; i++){
            int val = nums[i];
            int left = min_cache[i-1];
            if(max_cache[i+1] > left && val > max_cache[i+1]) return true;
            for(int j = i+1; j < len; j++){
                if(nums[j] > left && val > nums[j]) return true;
            }
        }
        return false;
    }

X. Left and Right Array,
http://bgmeow.xyz/2017/01/02/LeetCode-456/
http://www.alanshawn.com/leetcode-456-132-pattern/

We are actually looking for a 𝛬-shaped pattern in the array. For each element, we keep track of the minimal value to its left, and the maximal value that is smaller than the element to the right. If the value to the right is greater than the value to the left, we have found a 132 pattern.

    def find132pattern(self, nums):

"""

        :type nums: List[int]

        :rtype: bool

"""

        if len(nums) < 3:

            return False

        minLeft = [None] * len(nums)

        maxRight = [None] * len(nums)

        leftMin = nums[0]

        for i in range(0, len(nums)):

            if nums[i] < leftMin:

                leftMin = nums[i]

            minLeft[i] = leftMin

        rightHelper = []

        for i in range(len(nums) - 1, -1, -1):

            insertIndex = bisect.bisect_left(rightHelper, nums[i])

            #print('{},{}'.format(nums[i], insertIndex))

            if insertIndex != 0:

                maxRight[i] = rightHelper[insertIndex - 1]

            rightHelper.insert(insertIndex, nums[i])

        for i in range(len(nums)):

            #print('{},{},{}'.format(nums[i], minLeft[i], maxRight[i]))

            if minLeft[i] is not None and maxRight[i] is not None:

                if maxRight[i] > minLeft[i]:

                    return True

        return False

X. brute force
https://discuss.leetcode.com/topic/68242/java-solutions-from-o-n-3-to-o-n-for-132-pattern

I. Naive O(n^3) solution

simply check every (i, j, k) combination to see if there is any 132 pattern.

public boolean find132pattern(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            for (int k = j + 1; k < nums.length; k++) {
                if (nums[i] < nums[k] && nums[k] < nums[j]) return true;
            }
        }
    }
    return false;
}

II. Improved O(n^2) solution

To reduce the time complexity down to O(n^2), we need to do some observations. In the naive solution above, let's assume we have index j fixed, what should index i be so that it is most probable we will have a 132 pattern? Or in other words, what should i be so that we will be certain there is no such 132 pattern for combination (*, j, *) whenever there is no 132 pattern for combination of (i, j, *)? (Here * means any index before or after index j.)

The answer lies in the fact that once the first two numbers nums[i] and nums[j] are fixed, we are up to find the third number nums[k] which will be within the range (nums[i], nums[j]) (the two bounds are exclusive). Intuitively the larger the range is, the more likely there will be a number "falling into" it. Therefore we need to choose index i which will maximize the range (nums[i], nums[j]). Since the upper bound nums[j] is fixed, this is equivalent to minimizing the lower bound nums[i]. Thus it is clear ishould be the index of the minimum element of the subarray nums[0, j) (left inclusive, right exclusive).

Since we are scanning index j from the beginning of the input array nums, we can keep track of the minimum element of the subarray from index 0 up to j - 1 without rescanning it. Therefore the first two loops in the naive solution can be combined into one and leads to the following O(n^2) solution:

public boolean find132pattern(int[] nums) {
    for (int j = 0, min = Integer.MAX_VALUE; j < nums.length; j++) {
         min = Math.min(nums[j], min);
         if (min == nums[j]) continue;
         
         for (int k = nums.length - 1; k > j; k--) {
             if (min < nums[k] && nums[k] < nums[j]) return true;
         }
     }
     
     return false;
}

While this solution can be accepted, it runs slow. One obvious drawback is that in the second loop we are throwing away information about elements in the right part of nums that may be "useful" for later combinations. It turns out we can retain this "useful" information by applying the classic space-time tradeoff, which leads to the following O(n) time and O(n) space solution.
https://leetcode.com/articles/132-pattern/#approach-5-using-binary-search-accepted

Now, assume that we have somehow found a

nums[i],nums[j]

pair. Our task now reduces to finding out a

nums[k]

(

Kk>j>i)

, which falls in the range

(nums[i], nums[j])

. Now, to maximize the likelihood of a

nums[k]

falling in this range, we need to increase this range as much as possible. Since, we started off by fixing a

nums[j]

, the only option in our hand is to choose a minimum value of

nums[i]

given a particular

nums[j]

. Once, this pair

nums[i],nums[j]

, has been found out, we simply need to traverse beyond the index

j

to find if a

nums[k]

exists for this pair satisfying the 132 criteria.

Based on the above observations, while traversing over the

nums

array choosing various values of

nums[j]

, we simultaneously keep a track of the minimum element found so far(excluding

nums[j]

). This minimum element always serves as the

nums[i]

for the current

nums[j]

. Thus, we only need to traverse beyond the

j^{th}

index to check the

nums[k]

's to determine if any of them satisfies the 132 criteria.

III. Optimized O(n) solution

As I mentioned, to further reduce the time complexity, we need to record the "useful" information about elements in the right part of the input array nums. Since these elements are located at the right part of nums, it will be hard to do so if we are scanning the array from the beginning. So the idea is to scan it from the end while in the meantime keep track of the "useful" information. But still at each index j, we need to know the minimum element for subarray nums[0, j). This can be done by doing a pre-scan in the forward direction and memorize the results for each index in an auxiliary array (we will call the array as arr whose element arr[j] will denote the minimum element in the subarray nums[0, j)).

Until now we are kinda vague about the exact meaning of "useful" information, so let's try to be more specific. Assume we're currently scanning (from the end) the element with index j, our task is to find two elements nums[i] and nums[k] to determine if there exists a 132 pattern, with i < j < k. The left element nums[i], as it has been shown in part II, will be chosen as arr[j], the minimum element of subarray nums[0, j). What about the right element nums[k]?

The answer to that will address the meaning of "useful" information. First note we are only interested in elements that are greater than arr[j], so it is sensible to maintain only those elements. Second, among all these qualified elements, which one will be the most probable to fall into the range (nums[i], nums[j])? I would say it is the smallest one (i.e., if the smallest one is out of the range, all others will also be out of range). So to sum up, the "useful" information for current index j will be a collection of scanned elements that are greater than arr[j], and nums[k] will be chosen as the smallest one if the collection is not empty.

From the analyses above, it looks like we have to do some sorting stuff for the retained elements (or at least find a way to figure out its smallest element). Well, it turns out these elements will be sorted automatically due to the fact that arr[j'] >= arr[j] as long as j' < j. Here is how it goes, which is a proof by induction.

At the beginning we have an empty collection and of course it is sorted. Now suppose we are at index j and the corresponding collection is still sorted, let's see if it remains so at index j - 1. First we will check if nums[j] is greater than arr[j]. If not, we simply continue to j - 1. Since the collection is intact so it will be sorted at j - 1. Otherwise, we need to remove elements in the collection that are no greater than arr[j] (this is necessary because some smaller elements may be left over in the collection from previous steps). After removal, we then compare the first element in the collection with nums[j] to see if a 132 pattern has been found, provided the collection is not empty. If so, return true. Otherwise one of the following must be true: the collection is empty or nums[j] is no greater than the first element in the collection. In either case the collection is sorted. Now if we have arr[j - 1] < nums[j], we need to add nums[j] to the collection since it is a qualified number for arr[j - 1]. Again in either case the collection will remain sorted after addition (if it is empty, after addition there is only one element; otherwise since the added element is no greater than the first element in the collection before addition, it will become the new first element after addition and the collection stays sorted).

Here is the program with O(n) time and space complexity. There is one minor optimization based on the observation that the total number of elements in the collection will never exceed the total number of elements scanned so far. Therefore the right part of the arrarray can be used to serve as the collection. For time complexity, each element in the input array nums will be pushed into and popped out from the collection (or stack to be exact) at most once, the time complexity will be O(n) despite of the nested loop.

public boolean find132pattern(int[] nums) {
    int[] arr = Arrays.copyOf(nums, nums.length);

    for (int i = 1; i < nums.length; i++) {
        arr[i] = Math.min(nums[i - 1], arr[i - 1]);
    }
    
    for (int j = nums.length - 1, top = nums.length; j >= 0; j--) {
        if (nums[j] <= arr[j]) continue;
        while (top < nums.length && arr[top] <= arr[j]) top++;
        if (top < nums.length && nums[j] > arr[top]) return true;
        arr[--top] = nums[j];
    }
        
    return false;
}

https://t.du9l.com/2016/11/leetcode-456-132-pattern/

思路是遍历每一个可能的k值，然后找到它之前第一个（也就是距离最近的）比它大的数作为aj，然后再判断a0~aj-1之间的最小值是否小于ak。

之所以要找到“第一个”比它大的数，理由也很明显：要尽量扩大找ai的范围，否则可能会有false negative的情况。

思路很简单，关键是如何做到O(n)。因为遍历每一个k的过程就是O(n)的，所以要求后面两个步骤都是O(1)，也就是要预处理。预处理最小值很简单，开一个数组记录一下即可，空间复杂度O(n)。预处理“之前第一个比ak大的数（的位置）”就比较麻烦了，放在子算法里说，空间复杂度也是O(n)。

因此最终算法分三步：预处理a0~aj的最小值，预处理ak之前第一个大的数，遍历每一个可能的k。

要预处理每个数之前第一个比它大的数，用到了之前一个stack的奇技淫巧。方法是维护一个pair<数, 位置>的stack，其中数是递减的；对于数组从头到尾遍历，每个数先将栈顶比它小的数pop出去，如果pop完了栈空了，说明前面没有比它大的数，此时预处理结果为-1；否则预处理结果为栈顶数的位置。处理完之后将当前pair<数, 位置>也push进栈。

原理：因为要找到之前第一个比它大的数，如果栈顶的数比当前数还小，那对于它们之后的数来说，当前数更可能是比后面数大的结果，所以将栈顶pop出去。因为每个数最多进出栈一次，时间复杂度O(n)。

    bool find132pattern(vector<int>& nums) {

        if (nums.empty()) return false;

        int n = nums.size();

        vector<int> min1(n);

        min1[0] = nums[0];

        for (int i = 1; i < n; ++i) {

            min1[i] = min(min1[i-1], nums[i]);

}

        typedef pair<int, int> pii;

        stack<pii> s;

        vector<int> max1;

        for (int i = 0; i < n; ++i) {

            int I = nums[i];

            while (!s.empty() && s.top().first <= I) s.pop();

            if (s.empty()) {

                max1.push_back(-1);

            } else {

                max1.push_back(s.top().second);

}

            s.push(make_pair(I, i));

}

        for (int i = n-1; i >= 0; --i) {

            int I = nums[i];

            int j = max1[i];

            if (j == -1 || j == 0) continue;

            if (min1[j-1] < I) return true;

}

        return false;

}

在discuss中有一些更为精炼的方法。一些也是求范围的；另外一些是求出一个数左边的最小，再看右边有没有比左边最小大且比自己小的数

X. http://www.cnblogs.com/grandyang/p/6081984.html
这道题给我们了一个数组，让我们找到132的模式，就是第一个数小于第二第三个数，且第三个数小于第二个数。那么我们就按顺序来找这三个数，首先我们来找第一个数，这个数需要最小，那么我们如果发现当前数字大于等于后面一个数字，我们就往下继续遍历，直到当前数字小于下一个数字停止。然后我们找第二个数字，这个数字需要最大，那么如果我们发现当前数字小于等于下一个数字就继续遍历，直到当前数字大雨下一个数字停止。最后就找第三个数字，我们验证这个数字是否在之前两个数字的中间，如果没有找到，我们就从第二个数字的后面一个位置继续开始重新找这三个数字
https://www.jianshu.com/p/910fe372d9a0

该题利用到了栈这一数据结构。该题求解的是132 Pattern。栈中存储当前最大的数。同时设置一个值third。用于存储132中3位置的数。将给定的数组从后往前遍历，一旦当前数据大于栈中的数据就弹出栈。third存储弹出数据中最大的值。一旦当前遍历到的数据小于third则返回true。此时third记录着3位置的数据，栈中记录着2位置的数据，遍历到的数据为1位置上的数据。

public boolean find132pattern(int[] nums) {

if (nums == null || nums.length == 0)

return false;

boolean result = false;

int third = Integer.MIN_VALUE;

Stack<Integer> stack = new Stack<Integer>();

for (int i = nums.length - 1; i >= 0; i--) {

if (nums[i] < third)

return true;

while (!stack.isEmpty() && nums[i] > stack.peek()) {

third = Math.max(third, stack.pop());

}

stack.push(nums[i]);

}

return result;

}

X.
http://blog.csdn.net/mebiuw/article/details/53193012
public boolean find132pattern(int[] nums) { Stack<Range> stack = new Stack<>(); for(int num : nums) { Range cur = new Range(num, num); while(!stack.isEmpty() && cur.max > stack.peek().min) { cur.min = Math.min(stack.peek().min, cur.min); cur.max = Math.max(stack.peek().max, cur.max); stack.pop(); } stack.push(cur); if(stack.peek().min < num && num < stack.peek().max) return true; } return false; }
https://segmentfault.com/a/1190000007507137

维护一个pair, 里面有最大值和最小值。如果当前值小于pair的最小值，那么就将原来的pair压进去栈，然后在用这个新的pair的值再进行更新。如果当前值大于pair的最大值，首先这个值和原来在stack里面的那些pair进行比较，如果这个值比stack里面的值的max要大，就需要pop掉这个pair。如果没有适合返回的值，就重新更新当前的pair。

class Pair {

int min;

int max;

public Pair(int min, int max) {

this.min = min;

this.max = max;

}

public boolean find123Pattern(int[] nums) {

if (nums == null || nums.length < 3)

return false;

Pair cur = new Pair(nums[0], nums[0]);

Stack<Pair> stack = new Stack<>();

for (int i = 1; i < nums.length; i++) {

if (nums[i] < cur.min) {

stack.push(cur);

cur = new Pair(nums[i], nums[i]);

} else if (nums[i] > cur.max) {

while (!stack.isEmpty() && stack.peek().max <= nums[i]) {

stack.pop();

}

if (!stack.isEmpty() && stack.peek().max > nums[i]) {

return true;

}

cur.max = nums[i];

} else if (nums[i] > cur.min && nums[i] < cur.max) {

return true;

}

return false;

}

https://leetcode.com/problems/132-pattern/discuss/94077/java-on-solution-using-stack-in-detail-explanation

The idea is that we can use a stack to keep track of previous min-max intervals.

Here is the principle to maintain the stack:

For each number num in the array

If stack is empty:

push a new Pair of num into stack

If stack is not empty:

if num < stack.peek().min, push a new Pair of num into stack
if num >= stack.peek().min, we first pop() out the peek element, denoted as last
- if num < last.max, we are done, return true;
- if num >= last.max, we merge num into last, which means last.max = num.
  Once we update last, if stack is empty, we just push back last.
  However, the crucial part is:
  If stack is not empty, the updated last might:
  - Entirely covered stack.peek(), i.e. last.min < stack.peek().min (which is always true) && last.max >= stack.peek().max, in which case we keep popping out stack.peek().
  - Form a 1-3-2 pattern, we are done ,return true

So at any time in the stack, non-overlapping Pairs are formed in descending order by their min value, which means the min value of peek element in the stack is always the min value globally.

https://discuss.leetcode.com/topic/67816/o-n-time-o-n-space-java-solution-using-stack-13ms

You are absolutely right because intuition doesn't lead us to Stack solution for this problem.

At the very beginning, I tried to use two variables, i.e. min, max, to denote the min-max intervals, and update them as I encounter new numbers, but I soon found that only two variables cannot easily maintain the position information (as you update min and max, the previous ones lost).

So we need to keep "multiple min-max pairs" here. Then what can we use? We can use a List, which is definitely feasible. And what is the advantage of List? That is we can randomly access any position, but as I go along my thinking process to figure out how to maintain/merge different intervals, I found that we only need to fetch those intervals from the List sequentially, so List seems to be too "powerful" at this time, and Stack is a perfect LIFO container.

BTW, for all Stack questions, we can always use List, but Stack makes it easier to code and maintain

The idea is that we can use a stack to keep track of previous min-max intervals.

Here is the principle to maintain the stack:

For each number num in the array

If stack is empty:

push a new Pair of num into stack

If stack is not empty:

if num < stack.peek().min, push a new Pair of num into stack
if num > stack.peek().min, we first pop() out the peek element, denoted as last
- if num < last.max, we are done, return true;
- if num > last.max, we merge num into last, which means last.max = num.
  Once we update last, if stack is empty, we just push back last.
  However, the crucial part is:
  If stack is not empty, the updated last might:
  - Entirely covered stack.peek(), i.e. last.min < stack.peek().min (which is always true) && last.max > stack.peek().max, in which case we keep popping out stack.peek().
  - Form a 1-3-2 pattern, we are done ,return true

So at any time in the stack, non-overlapping Pairs are formed in descending order by their min value, which means the min value of peek element in the stack is always the min value globally.
i = 6, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 9, S3 candidate = None, Stack = Empty
i = 5, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 7, S3 candidate = None, Stack = [9]
i = 4, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 10, S3 candidate = None, Stack = [9,7]
i = 3, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 9, S3 candidate = 9, Stack = [10]
i = 2, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 8, S3 candidate = 9, Stack = [10,9] We have 8<9, sequence found!

   class Pair{
        int min, max;
        public Pair(int min, int max){
            this.min = min;
            this.max = max;
        }
    }
    public boolean find132pattern(int[] nums) {
        Stack<Pair> stack = new Stack();
        for(int n: nums){
            if(stack.isEmpty() || n <stack.peek().min ) stack.push(new Pair(n,n));
            else if(n > stack.peek().min){ 
                Pair last = stack.pop();
                if(n < last.max) return true;
                else {
                    last.max = n;
                    while(!stack.isEmpty() && n >= stack.peek().max) stack.pop();
                    // At this time, n < stack.peek().max (if stack not empty)
                    if(!stack.isEmpty() && stack.peek().min < n) return true;
                    stack.push(last);
                }
                
            }
        }
        return false;
    }

https://www.jianshu.com/p/ab0e2d42ade0

利用栈来保存之前的min-max intervals
If stack is empty:

push a new Pair of num into stack

If stack is not empty:

if num < stack.peek().min, push a new Pair of num into stack
if num >= stack.peek().min, we first pop() out the peek element, denoted as last
- if num < last.max, we are done, return true;
- if num >= last.max, we merge num into last, which means last.max = num.
  Once we update last, if stack is empty, we just push back last.
  However, the crucial part is:
  If stack is not empty, the updated last might:
  - Entirely covered stack.peek(), i.e. last.min < stack.peek().min (which is always true) && last.max >= stack.peek().max, in which case we keep popping out stack.peek().
  - Form a 1-3-2 pattern, we are done ,return true

目的：保证stack里面保存的pair是无overlap的，且是按照min-value递减的。所以peek()处的min为全局最小值。

class Pair {

int min, max;

public Pair(int min, int max) {

this.min = min;

this.max = max;

}

public boolean find132pattern(int[] nums) {

Stack<Pair> stack = new Stack<>();

for (int num : nums) {

if (stack.isEmpty() || num < stack.peek().min)

stack.push(new Pair(num, num));

else if (num > stack.peek().min) {

Pair last = stack.pop();

if (num < last.max)

return true;

last.max = num;

while (!stack.isEmpty() && num >= stack.peek().max)

stack.pop();

if (!stack.isEmpty() && stack.peek().min < num)

return true;

stack.push(last);

}

return false;

}

X. nlogn
http://www.voidcn.com/article/p-bdcwkzug-oe.html

用一个数组mi记录前缀最小值，从后往前遍历，当前为i，用一个set记录i之后出现（已经遍历过）的数，则如果在set中找到在(mi[i-1],num[i])之间的数就存在。复杂度O(n*lgn)

    bool find132pattern(vector<int>& nums) {
        int n=nums.size();
        if(n<=2) return false;
        vector<int>mi(n);
        mi[0]=nums[0];
        for (int i = 1; i <n ; ++i) {
            mi[i]=min(mi[i-1],nums[i]);
        }
        set<int>ri;
        set<int>::iterator it;
        ri.insert(nums[n-1]);
        for (int i = n-2; i >0 ; --i) {
            if(nums[i]>mi[i-1]) {
                it=ri.upper_bound(mi[i-1]);
                if(it!=ri.end()&&*it<nums[i]) return true;
            }
            ri.insert(nums[i]);
        }
        return false;
    }

Approach #5 Using Binary Search [Accepted]:

In the last approach, we've made use of a separate

stack

to push and pop the

nums[k]

's. But, we can also note that when we reach the index

j

while scanning backwards for finding

nums[k]

, the

stack

can contain atmost

n-j-1

elements. Here,

n

refers to the number of elements in

nums

array.

We can also note that this is the same number of elements which lie beyond the

j^{th}

index in

nums

array. We also know that these elements lying beyond the

j^{th}

index won't be needed in the future ever again. Thus, we can make use of this space in

nums

array instead of using a separate

stack

. The rest of the process can be carried on in the same manner as discussed in the last approach.

We can try to go for another optimization here. Since, we've got an array for storing the potential

nums[k]

values now, we need not do the popping process for a

min[j]

to find an element just larger than

min[j]

from amongst these potential values.

Instead, we can make use of Binary Search to directly find an element, which is just larger than

min[j]

in the required interval, if it exists. If such an element is found, we can compare it with

nums[j]

to check the 132 criteria. Otherwise, we continue the process as in the last approach.

https://medium.com/@ChYuan/leetcode-no-456-132-pattern-%E5%BF%83%E5%BE%97-medium-16fe9b11c4e3

和第四個方法類似，但是少了第四個方法的 stack，因為可以發現 stack存的數都是 j 後面的數字，只拿來找 nums[k] 而以，所以就重複利用這個空間，並且用 binary search 方式尋找 nums[k] 符合 132 pattern

public boolean find132pattern(int[] nums) {

if (nums.length < 3)

return false;

int[] min = new int[nums.length];

min[0] = nums[0];

for (int i = 1; i < nums.length; i++)

min[i] = Math.min(min[i - 1], nums[i]);

for (int j = nums.length - 1, k = nums.length; j >= 0; j--) {

if (nums[j] > min[j]) {

k = Arrays.binarySearch(nums, k, nums.length, min[j] + 1);

if (k < 0)

k = -1 - k;

if (k < nums.length && nums[k] < nums[j])

return true;

nums[--k] = nums[j];

}

return false;

}

Brute Force
O(n^2)

public boolean find132pattern(int[] nums) {

int min_i = Integer.MAX_VALUE;

for (int j = 0; j < nums.length - 1; j++) {

min_i = Math.min(min_i, nums[j]);

for (int k = j + 1; k < nums.length; k++) {

if (nums[k] < nums[j] && min_i < nums[k])

return true;

}

return false;

}

https://blog.csdn.net/yt4766269/article/details/53495785

于是考虑到，并不需要遍历每一个三元组，只需要找到头尾两个值，看中间是否存在一个值大于头尾，并且尾值大于头值，这个过程直接通过遍历取max就可以得到。

于是时间复杂度被降低到了O（n2）。

public boolean find132pattern(int[] nums) {
if(nums.length<3)
return false;
for(int i = 0;i<nums.length;i++){
int max = Integer.MIN_VALUE;
for(int j = i+1;j<nums.length;j++){
if(max<nums[j]){
max = nums[j];
}
if(max>nums[j]&&max>nums[i]&&nums[i]<nums[j]){
return true;
}
}
}
return false;
}
O(n^3)

public boolean find132pattern(int[] nums) {

for (int i = 0; i < nums.length - 2; i++) {

for (int j = i + 1; j < nums.length - 1; j++) {

for (int k = j + 1; k < nums.length; k++) {

if (nums[k] > nums[i] && nums[j] > nums[k])

return true;

}

return false;

}

Approach #2 Better Brute Force [Accepted]

Time complexity :

O(n^2)

. Two loops are used to find the

nums[j],nums[k]

pairs. Here,

n

refers to the size of

nums

array.

We can note that for a particular number

nums[j]

chosen as 2nd element in the 132 pattern, if we don't consider

nums[k]

(the 3rd element) for the time being, our job is to find out the first element,

nums[i]

(

i

) which is lesser than

nums[j]

Now, assume that we have somehow found a

nums[i],nums[j]

pair. Our task now reduces to finding out a

nums[k]

(

Kk&gt;j&gt;i)

, which falls in the range

(nums[i], nums[j])

. Now, to maximize the likelihood of a

nums[k]

falling in this range, we need to increase this range as much as possible.

Since, we started off by fixing a

nums[j]

, the only option in our hand is to choose a minimum value of

nums[i]

given a particular

nums[j]

. Once, this pair

nums[i],nums[j]

, has been found out, we simply need to traverse beyond the index

j

to find if a

nums[k]

exists for this pair satisfying the 132 criteria.

Based on the above observations, while traversing over the

nums

array choosing various values of

nums[j]

, we simultaneously keep a track of the minimum element found so far(excluding

nums[j]

). This minimum element always serves as the

nums[i]

for the current

nums[j]

. Thus, we only need to traverse beyond the

j^{th}

index to check the

nums[k]

's to determine if any of them satisfies the 132 criteria.

public boolean find132pattern(int[] nums) {

int min_i = Integer.MAX_VALUE;

for (int j = 0; j < nums.length - 1; j++) {

min_i = Math.min(min_i, nums[j]);

for (int k = j + 1; k < nums.length; k++) {

if (nums[k] < nums[j] && min_i < nums[k])

return true;

}

return false;

}

https://gist.github.com/aligator4sah/7b984d25d7551944b2e51f845c6e6803

https://leetcode.com/problems/132-pattern/discuss/94091/Easy-Java-solution-using-BST-with-explanation

public boolean find13Pattern(int nums[]){
        if(nums.length < 2) return false;
        int min = nums[0];
        for(int i = 1;i<nums.length;i++){
               if(nums[i]>min) return true;
               min = Math.min(min, nums[i]);
        }
        return false;
}

LeetCode 456 - 132 Pattern

Labels

Popular Posts