问答

当前位置

Google 面试题 | 132 模式

  • Ta: 克里斯本-助教

题目描述

现有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[k]。那么我们可以挑选a[j]左边的最小值和a[j]右边的最大值(前提都需要小于a[j])作为a[i]和a[k]进行比较。假如这样子都无法满足a[i]<a[k]的条件那显然是无解的。

2.经过上述分析,问题从三层循环简化到了两层循环(一层对j循环,一层扫描数组寻找最小值与最大值),但显然还是不够简化。因为在第二层循环耗费了太多时间,对每一个j都找一遍最小值和最大值太浪费时间。我们思考可不可以通过引入额外的记录空间的方式进行优化(以空间换时间)。对于最小值比较简单,我们可以建立一个数组min,min[j]代表a[j]左侧的数中的最小值。注意这里我们可以没有要求min[j]比a[j]小(否则是无法在O(n)内实现的),因为我们之后还需要对j扫描,完全可以在那时加入判断,只取min[j]<a[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<ak即可。这里我们把最大值和最小值都求出来进行了求解。更优化的方案可以不求最小值,因为在求最大值的过程中确定了a[j]与a[k]后,只需继续向前找,找到一个符合条件的a[i]即可,并不一定非要找到最小的。但是为了思路的清晰,参考程序中依然给出了有最小值的版本。

参考程序

0 个回复

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1