【单调栈】个人练习-Leetcode-456. 132 Pattern

题目链接：https://leetcode.cn/problems/132-pattern/

题目大意：给出一个数列nums[]，判断是否能找到这样的结构：下标i < j < k，并且元素nums[i] < nums[k] < nums[j]，即所谓【132】结构。

思路：应该是用单调栈做，初始的想法是用单调递增栈维护1 3，枚举2，思路是正确的，然而存在弊端：每个被遍历的元素要和所有的栈的头和尾（1和3）比较，夹在中间才能满足。然而如果这样的栈很多，实际上会超出时间限制。就算我做了改良：只保留【区间跨度最大】的栈，也依然超时。

原来的代码

class Solution {
public:bool find132pattern(vector<int>& nums) {vector<vector<int>> acs;int N = nums.size();vector<int> tmp(1, nums[0]);acs.push_back(tmp);for (int i = 1; i < N; i++) {for (auto st : acs) {if (nums[i] < st.back() && nums[i] > st[0])return true;}if (nums[i] > acs.back().back()) {acs.back().push_back(nums[i]);for (int j = 0; j < acs.size()-1; j++) {if (acs.back()[0] < acs[j][0] && acs.back().back() > acs[j].back()) {acs.erase(acs.begin()+j, acs.begin()+j+1);j--;}}}else if (nums[i] < acs.back().back()) {if (acs.back().size() < 2)acs.pop_back();vector<int> tmp(1, nums[i]);acs.push_back(tmp);}else;}return false;}
};

看了题解才发现我离正确的解法已经很近了。其实可以【枚举1】，这是因为如果枚举1，我们同样只需要用单调递减栈来维护2, 3。

具体做法是，从后往前遍历，刚开始可能会觉得奇怪，既然结构是【132】，从后往前不应该是【单调递增栈】吗。实际上，使用【递减栈】的目的，是将2出栈。

我们用一个数字k来记录所谓的2，并且保留最大的2，那么从后往前遍历时，为了维护递减栈，当栈顶元素是2，而下一个元素是3时，就会发生【弹出】，2被弹出，3被压入栈。

此时，2记录在k中，3留在栈顶。继续遍历。如果某个数字nums[i]比k小，说明这个数小于2，那么它当然也小于3，同时，又因为它在2, 3的左边，并且，2是被弹出的，3是在栈里的，明显2在3的右边，于是这个数就可以作为1，满足【132结构】

总结：利用单调栈维护【32】，其中3存在栈里，2存在一个int中，遍历寻找合适的1。

完整代码

class Solution {
public:bool find132pattern(vector<int>& nums) {int N = nums.size();int k = INT_MIN;vector<int> st;for (int i = N-1; i >= 0; i--) {if (nums[i] < k)return true;while (st.size() && st.back() < nums[i]) {k = max(k, st.back());st.pop_back();}st.push_back(nums[i]);}return false;}
};