撰文 | ben助教
编辑 | Francesca jin
专栏 | 九章算法
对n个数的序列，a1，a2，……，an，判断是否存在i
样例1
输入： [1,2,3,4]
输出： False
样例2
输入： [3,1,4,2]
输出： True
说明： [1,4,2]是一个132模式
样例3
输入： [-1,3,2,0]
输出： True
说明： [-1,3,2]，[-1,3,0]，[-1,2,0]均为132模式
枚举i
a. 令min(j)为a(1)，a(2)，……，a(j)中的最小值，那么如果[a(i),a(j),a(k)]为一个132模式，则[min(j-1),a(j),a(k)]也必为132模式，反之，如果[min(j-1),a(j),a(k)]不是132模式，那么对于任意i
b. min(j)可以用O(n)的时间递推出来，再枚举j,k，判断是否有min(j-1)
a.
与方法2相似，我们也可以省去对k的枚举。令max(j)为a(j+1)，a(j+2)，……，a(n)中小于a(j)的最大值，那么a(k)即可用max(j)代替。与方法2中不同的是，此处要求的不是a(j)以后的数中的最大值，而是要小于a(j)的最大值，这个问题当然可以用线段树或者平衡树来处理，但过于复杂，其实用栈就可以处理这个问题。
b. 我们从后往前枚举j，如果栈顶元素小于a(j)，则将栈顶元素出栈，直到栈为空或栈顶元素不小于a(j)，再将a(j)压入栈。这样就保证了，栈中元素由栈顶到栈底是非降序的，那么在a(j)入栈前最后一个出栈的就是栈中小于a(j)的最大值。
c. 有一个小问题是，实际的max(j)可能在枚举到j之前就已经出栈了，而导致实际得到的值并非是a(j)以后小于a(j)的最大值，而只是枚举到j时的栈中小于a(j)的最大值，但这对于原问题的求解来说没有影响，故仍把该值记为max(j)，有兴趣的读者可以自己分析一下。
d. 得到max(j)后，判断是否有min(j-1)
Follow up：如何快速统计序列中132模式的组数？
这里提供一个思路：从后往前枚举i，同时维护一组键值对{a(k),ans(k)}，ans(k)表示满足ia(k)的组数，故a(i)对答案的贡献为所有大于a(i)的a(k)对应的ans(k)之和；加入a(i)后，则将对所有小于a(i)的a(k)对应的ans(k)增加1，同时增加一组键值对{a(i),0}。
这个问题主要考察对问题的分析预处理的能力，三种不同时间复杂度的算法可以把面试者分成三类，是一道适合面试的好题。给出第二种算法可以hire，给出第三种可以strong hire。
http://www.lintcode.com/zh-cn/problem/implement-stack/
http://www.jiuzhang.com/solution/132-patterns/
回复“简历”，查看简历撰写指南，获取“简历模板”
回复“冷冻期”，查看北美各大IT企业冷冻期信息和注意事项
回复“Career”, 查看Caireer Fair 攻略 check list
回复“薪资”，查看北美各大IT企业New Grades Engineer 薪资水平；
回复“项目”，查看7-14天可以搞定的小项目推荐
回复“评分”，查看系统设计评分指南
回复“behavior”，查看behavior interview指南
回复“晋升”，查看Engineer晋升机制
算法强化班 | 面向Facebook/Google等求职者
各类IT企业的面试算法难度及风格
如何解决中等难度以上的算法题
如何解决follow up问题
正在报名中！
报名登陆官网 www.jiuzhang.com
或点击文末“阅读原文”
