題目描述

題目分析

我覺得這道題應該是我做過最難的中等題之一了，這是昨天的每日一題，但是昨天用nlogn的做法做出來以后在看題解，發現有些看不懂（覺得題解有點故弄玄虛）。然后今天中午又花了一點時間才搞懂，感覺從這道題里面學到一點東西。

剛拿到這道題的時候我沒有什么思路，第一想法當然是$n^3$的暴力，但是顯然是不行的，第二想法是，用線段樹維護區間最大值，然后遍歷1和2，這樣的復雜度是$n^{2}logn$，雖然好了一點但仍然會超時。我自己沒有想到枚舉一個，然后通過數據結構求其他兩個的思路，覺得這方面有點欠缺，即這種思路的轉換，仿佛變量比較多就必須每一個都枚舉才可以。

遍歷3，用紅黑樹維護2

看到題解從左往右枚舉3，然后用一個變量保存1（左邊的最小值），用一個紅黑樹（使用set）保存右邊所有的值，在里面查找比1大比3小的數。這樣的做法很符合直覺。
我用這樣的思路很快寫了一個和題解差不多的代碼：

O(nlogn)代碼

class Solution {
public:bool find132pattern(vector<int>& nums) {using vector_size = vector<int>::size_type;vector_size n = nums.size();if (n < 3) return false;int left_min = nums[0];multiset<int> right_all(nums.begin() + 2, nums.end());for (vector_size i = 1; i < n - 1; ++i) {if (left_min < nums[i]) {auto iter = right_all.upper_bound(left_min);if (iter != right_all.end() && *iter < nums[i]) {return true;}}left_min = min(left_min, nums[i]);right_all.erase(right_all.find(nums[i + 1]));}return false;}
};

紅黑樹的查找和刪除都是logn的，真不錯。

其他思路都統統使用了單調棧，其實單調棧本身的非常簡單，就是一個棧，里面是有序的，如果一個新加入的元素破壞了順序，就彈出，直到不破壞為止，再入棧。

遍歷1，用單調棧維護3和2

這道題的神奇之處在于用了一個遞減的單調棧，并用一個變量保存所有出棧元素的最大值，因為入棧、出棧操作的先后順序導致這個出棧元素的最大值肯定比棧中某個元素小而且在其前面，因為是那個元素將它出棧的，而這樣就得到了3和2，我們只要遍歷到比2小的1即可。這種方法的復雜度應該是最低的。

O(n)代碼

class Solution {
public:bool find132pattern(vector<int>& nums) {int n = nums.size();if (n < 3) return false;stack<int> stk;     //單調棧int max_pop = INT_MIN;        //彈出的元素的最大值for (int i = n - 1; i >= 0; --i) {if (max_pop != INT_MIN) {if (nums[i] < max_pop) return true;}while (!stk.empty() && nums[i] > stk.top()) {max_pop = max(max_pop, stk.top());stk.pop();}stk.push(nums[i]);}return false;}
};

剛才習慣性地使用vector<int>::size_type類型，但是循環的時候卻RE，這是因為size_type類型是一個unsigned類型，在--到-1的時候會變成一個非常大的數字導致死循環。應該盡量還是用int才好。

遍歷3，用單調棧維護2，用前綴數組維護1

雖然同樣是使用單調棧解決問題，但是用單調棧維護2的思路則和上面完全不同。我在看題解的時候一度非常迷惑，但是想明白原理以后才發現原來兩者之間沒有什么關系。

上面已經提到了，上面的解法的精髓在于維護了所有彈出元素的最大值，通過入棧、出棧的邏輯順序得到了數據的物理順序。但是現在這種解法則是完全不一樣的角度。

我們用一個前綴數組處理出任意位置左邊的最小值，得到1，用單調棧維護右邊的比本身3小的最大值，得到2，通過判斷1和2的大小來決定是否存在132序列。

問題的難點在于如何用單調棧維護右邊比當前遍歷到的3小的最大值，做法如下：將把當前值插入到單調棧中彈出的數據的最大值作為2。

我認為難以理解的地方在于，把一些比較小的數組彈出了，怎么能夠保證后面不會用到這些數字呢？

想要理解，可以用一個簡單的數學歸納：

1. 初始的時候棧中是有元素的
2. 新插入的當前元素可能沒有進行彈出操作，這意味著右邊全都是比當前值大的數字
3. 當第一次插入x發生彈出時，我們保存了彈出元素的最大值right_max，并且和其左邊最小值left_min進行比較，如果right_max>left_min，則出現132序列，如果沒有出現，則意味著x左邊全部元素大于等于right_max，也就是說right_max以及其他這次彈出的數據無論如何都不會成為2了，因此可以丟棄。

如果理解了上面的話，代碼就比較簡單了：

O(nlogn)代碼

class Solution {
public:bool find132pattern(vector<int>& nums) {int n = nums.size();if (n < 3) return false;stack<int> stk;     //單調棧維護2int max_pop;        //一次pop的最大值vector<int> left_min;left_min.reserve(nums.size());left_min.push_back(INT_MAX);for (int i = 1; i <n; ++i) {left_min[i] = min(left_min[i - 1], nums[i - 1]);}stk.push(nums[n - 1]);for (int i = n - 2; i >= 0; --i) {max_pop = INT_MIN;while (!stk.empty() && nums[i] > stk.top()) {max_pop = max(max_pop, stk.top());stk.pop();}if (left_min[i] < max_pop) return true;stk.push(nums[i]);}return false;}
};

時間復雜度應該是比第二種解法要高一個O(n)項