题目描述

对n个数的序列，a1，a2，……，an，判断是否存在i<j<k，使得ai<ak<aj（这样的[ai,aj,ak]被称为132模式）。n不超过15000。

样例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模式

解题思路分析

1.一个显而易见的暴力方法是

枚举i<j<k，再判断是否有a(i)<a(k)<a(j)成立。这样做的时间复杂度为O(n^3)，对于题目给出的n的大小是无法接受的。

2.用min(j-1)代替a(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<j，[a(i),a(j),a(k)]都不会是132模式。

b. min(j)可以用O(n)的时间递推出来，再枚举j,k，判断是否有min(j-1)<a(j)<a(k)，时间复杂度为O(n^2)。

3.用max(j)代替a(k)

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)<max(j)，如果成立则存在132模式，否则继续向前枚举j，如果对于所有的j均不成立，则不存在132模式。这样，时间复杂度为O(n)。

4.Follow up：如何快速统计序列中132模式的组数？

这里提供一个思路：从后往前枚举i，同时维护一组键值对{a(k),ans(k)}，ans(k)表示满足i a(k)的组数，故a(i)对答案的贡献为所有大于a(i)的a(k)对应的ans(k)之和；加入a(i)后，则将对所有小于a(i)的a(k)对应的ans(k)增加1，同时增加一组键值对{a(i),0}。

参考程序

面试官角度分析

这个问题主要考察对问题的分析预处理的能力，三种不同时间复杂度的算法可以把面试者分成三类，是一道适合面试的好题。给出第二种算法可以hire，给出第三种可以strong hire。