problem:https://leetcode.com/problems/132-pattern/
昨晚睡觉前想了一下，今早写好后交了一下居然过了。
我的想法是维护用一个数据结构来维护到目前为止出现的“13”pattern，为了减少计算量，把一些可能的“13”pattern合并，比如对于一个递增的数组：
2,3,4,5,6
合并后的“13”pattern就是 “26”。
对于以上数组，下一个数字只可能有这几种情况：
(1) 比最大的数<6>还大 —> 直接和pattern合并
(2) 处在最小数<2>和最小数<6>之间 —> 找到了答案
(3) 等于最大数<6>或最小数<2> —> 无事发生，继续执行
(4) 小于最小数<2>,当前pattern不再改变，把该数作为新的pattern的最小值来维护
对于每个新出现的数字，都在目前已有的"13"pattern中查询，它是否满足大于pattern"1"，并且小于pattern"3"，如果满足，就返回true。
总之，就是一个不断维护和查询的过程。
由于查询的复杂度和pattern数组的长度有关，所以不能算是O(N)算法，速度只打败了30%多，感觉应该有优化空间。（主要原因应该是，用如下的方法可能会维护冗余的pattern）
class Solution { public: vector<int> sta; bool find132pattern(vector<int>& nums) { for (int i = 0; i < nums.size(); i++) { if (sta.empty()) { sta.push_back(nums[i]); } else { // check valid for (int k = 1; k < sta.size(); k += 2) { if (nums[i] > sta[k - 1] && nums[i] < sta[k]) { return true; } } // even number, find the first number if (sta.size() % 2 == 0) { if (nums[i] > sta.back()) { sta.pop_back(); sta.push_back(nums[i]); } else if(nums[i] < sta[sta.size() - 2]) { sta.push_back(nums[i]); } } // odd number, find the second number else { if (nums[i] > sta.back()) { sta.push_back(nums[i]); } else { sta.pop_back(); sta.push_back(nums[i]); } } } } return false; } };
原文：https://www.cnblogs.com/fish1996/p/11262973.html