Google 面试题 | 132 模式

现有n个整数a[1], a[2], ..., a[n]，若这n个整数中有子序列ai, aj, ak满足条件i < j < k和a[i] < a[k] < a[j]，那我们称这个子序列为132模式。设计算法检查一个整数数组中是否存在132模式。

注：n不超过15,000。

Example 1

输入: [1, 2, 3, 4]

输出: False

Example 2

输入: [3, 1, 4, 2]
输出: True

Example 3

输入: [-1, 3, 2, 0]

输出: True

解释: 此序列中存在132模式的子序列[-1, 3, 2]，[-1, 3, 0]和[-1, 2, 0]。

1.初看这道题感觉不难但捉不到思路。当然有一种做法可以不让你拿0分，那就是三重循环分析遍所有的组合（笑）。这肯定是不可取的。我们试着简化这个问题的描述。直觉上感觉这个问题变化的量太多，a[i]、a[j]、a[k]都在变化，我们试着固定一个数。我们选择固定a[j]，因为a[j]在次序上处于中间，可以确定另两个数的范围。那这样问题就变为在a[j]的左边找到一个数比它小的数a[i]，右边找到一个比它小的数a[k]，满足a[i]。那么我们可以挑选a[j]左边的最小值和a[j]右边的最大值（前提都需要小于a[j]）作为a[i]和a[k]进行比较。假如这样子都无法满足a[i]

2.经过上述分析，问题从三层循环简化到了两层循环（一层对j循环，一层扫描数组寻找最小值与最大值），但显然还是不够简化。因为在第二层循环耗费了太多时间，对每一个j都找一遍最小值和最大值太浪费时间。我们思考可不可以通过引入额外的记录空间的方式进行优化（以空间换时间）。对于最小值比较简单，我们可以建立一个数组min，min[j]代表a[j]左侧的数中的最小值。注意这里我们可以没有要求min[j]比a[j]小（否则是无法在O(n)内实现的），因为我们之后还需要对j扫描，完全可以在那时加入判断，只取min[j]在这种情况下min[j]就是a[j]左侧比a[j]小的数中的最小值了。

3.而对于最大值则稍微复杂，它并不能套用上面的方法，因为对于最小值，min[j]>=a[j]时一定不存在我们要找的最小值（因为a[j]左侧就没有比它小的数了）。而max[j]>=a[j]时，是可能有我们需要的最大值的，只是这个最大值被一个a[j]右端大于a[j]的数掩盖了。考虑到最大值需要从右端开始扫描，我们可以建立一个栈，把从右端扫描过来的数据都压入栈中（使用栈是因为需要先进先出）。对于这个栈的要求是，当循环到a[j]时先将其与栈顶的数比较，如果栈空或者比栈顶的数小便将其压栈（基于这条规则可以推出这个栈本身是自顶到底递增的，a[j]若小于栈顶的数，证明a[j]小于之前扫描过的所有数，并不是我们所需要的）。当a[j]大于栈顶的数时，便开始将小于a[j]的数全部弹栈，之后再将a[j]压入栈。因为之前已经说明了这个栈自顶到底是递增的，扫描又是从右端开始的，所以最后一个被弹出来的数便是a[j]右侧比a[j]小的数中的最大值了。

4.有了这两个数据，基本也就大功告成了，只需让两者比较大小关系，满足ai。这里我们把最大值和最小值都求出来进行了求解。更优化的方案可以不求最小值，因为在求最大值的过程中确定了a[j]与a[k]后，只需继续向前找，找到一个符合条件的a[i]即可，并不一定非要找到最小的。但是为了思路的清晰，参考程序中依然给出了有最小值的版本。