456. 132 Pattern
思路 采用贪婪原则，从后往前遍历数组，维持一个从栈底到栈顶的递减栈，让s2尽可能地大（这样找到s1 < s2时就可以返回true了）。 所以s2的寻找分两步：
- 找到一个s2
- 尽可能地让s2变大
算法 从后往前遍历数组，维持一个从栈底到栈顶的递减栈。 每次遇到一个数，如果比栈顶大，就循环把栈顶弹出，并且把s2设置为最后弹出的数（因为维护的是递减栈，最后弹出的数是比当前数小的数中最大的，也就是说，它是s2的最佳候补）。 由于s2每次都被设置为被弹出的数，而且这些数字都比新栈顶小，可以发现，栈里的元素都比s2大，也是遍历过的数中比s2大的所有数，且其中至少有一个数是可以作为s3的（这一段助于理解，意思是栈内的数包含了s2的所有候补）。 也就是说，当s2被设置/更新的时候，一定已经找到了一个s3（至于是多少并不重要）。所以我们如果遇到某个数小于s2，就说明找到了s1，就可以返回true了。所以在遍历的过程中我们主要做2件事：
- 设置/更新s2
- 寻找s1 代码
class Solution {
public:
bool find132pattern(vector<int>& nums) {
stack<int> st;
int s2 = INT_MIN;
auto it = nums.rbegin();
while (it != nums.rend()) {
int cur = *it;
if (cur < s2) {
return true;
} else {
while (!st.empty() && st.top() < cur) {
s2 = st.top();
st.pop();
}
st.push(cur);
it++;
}
}
return false;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.09.19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读