本篇要來探討的是 Leetcode #456 132 Pattern

132 Pattern 代表要找出三個 element ，其 Index 順序為 i<j<k ，但是 nums[j] > nums[k] 且 nums[k] > nums[i] 。

方法 0 Brute Force

找出三筆資料所組成的所有組合，並確認是不是屬於 132 Pattern ，如果是，回傳 true ，反之，回傳 false 。

Time Complexity O(n^3)

Space Complexity O(1)

方法 1 Better Brute Force

方法 0 的暴力解需要用到三個迴圈，嘗試將時間複雜度再降低，132 Pattern 中 nums[i] 如果越小，越有力於找到後面的 (j, k) pair ，隨著走訪 input array ，只需要關注到目前為止最小的數來做為 nums[i] ，所有可能的 (j, k) pair 可以使用兩個迴圈即可。

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int min = INT_MAX;
        // Try to Find all possible (j, k) pair
        for (int j=0; j<nums.size()-1; j++) {
            for (int k = j+1; k < nums.size(); k++) {
                if (nums[j] > nums[k] && nums[k] > min) return true;
                min = std::min (min, nums[j]);
            }
        }
        return false;
    }
};

Time Complexity O(n^2)

Space Complexity O(1)

方法 2 Monotonic Stack

題目很複雜，所以試著將問題簡化成兩個問題

132 Pattern 中，先找出 32 pattern ，再來將 nums[i] 跟 nums[j], nums[k] 做比較。

以下為了講解方便，將以 n1, n2 和 n3 來替代 nums[i], nums[j] 和 nums[k] 。

32 Pattern

思考一下怎麼找出 32 Pattern， 32 Pattern 的條件為 n2 > n3 ，試想 n3 越大越好 ，這樣越容易找到 n1 來符合題目要求，使用 stack 並由後往前走訪能夠幫助我們找出更大的 n3 ，每個數都是可能作為 n3 的可能選擇，但只有遇到符合 23 pattern 的 n2 時候，才能真正將 stack 內的數作為 n3 ，還沒有遇到 "夠大的” n2 時候，那些更大的 candidate of n3 需要被保留在 stack 內，且越大的 n3 應該要在 stack 底部，因此會採取 Decreasing Monotonic stack 。

找出 n1

當由右往左來走訪時，可以持續找出更大的 (n2, n3) pair ，一旦遇到的數小於已經找出來的 n3 ，就代表找到符合 132 Pattern 的組合了。

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

Time Complexity O (n)

Space Complexity O (n)

方法 3 Monotonic Stack

以下為了講解方便，將以 n1, n2 和 n3 來替代 nums[i], nums[j] 和 nums[k] 。

試著將問題簡化成兩個問題:

1. 如果有了 13 pattern ，那每次遇到的新元素只要跟 n1 和 n2 做比較即可確認是否找到 132 pattern 。
2. 該如何找出 13 pattern ? 在走訪 array 時候，可以從中選出 n1 和 n2 ， n1 和 n2 會有許多的可能性，可以利用 stack 幫助我們保留住可以用且值得留的 (n1, n2) 。

為何選擇 decreasing stack ?

stack 的目的在於幫助找到更好的 n2 ，什麼是更好的 n2 ? 那就是 n2 越大，越有助於找到 132 Pattern ，回到 stack 的本質， stack 屬於 LIFO ，越好的 n2 應該要越不容易被 pop ，也就是盡可能保留在 stack 底層，所以會選擇 decreasing stack 。

隨著依序讀取 input array ，執行演算法如下:

1. 如果新元素大於 stack 頂端的 n2 ，代表找到更大的 n2 ，更小的 n2 留著也沒有幫助，可以直接 pop 掉 。
2. 如果 stack 不為空，代表 stack 內存有之前保存的 (n1, n2) pair ，新元素可以當作 n3 與 (n1, n2) 做比較，確認是否符合 132 pattern 。
3. 新的元素也可以作為 (n1, n2) pair ， 將當前元素組成的 pair 放到 stack 內。
4. n1 作為 132 pattern 中最小的值，肯定是越小越好， n1 永遠是到目前為止遇到最小的值，每拜訪一個新的數，就更新最小值以便作為後面新的 pair 的 n1 。

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        // Decreasing stack with (n1, n2) pair
        stack<pair<int, int>> st;
        int curr_min = INT_MAX;
        for (int i=0; i<nums.size(); i++) {

            while (!st.empty() && nums[i] >= st.top().second) {
                st.pop();
            }

            if (!st.empty() && nums[i] < st.top().second 
                && nums[i] > st.top().first) {
                return true;
            }

            st.push ({curr_min, nums[i]});
            curr_min = std::min (curr_min, nums[i]);
        }
        return false;
    }
};

Time Complexity O (n)
Space Complexity O (n)