算法随笔_33: 132模式

上一篇:算法随笔_32: 移掉k位数字-CSDN博客

=====

题目描述如下:

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,4]
输出：false
解释：序列中不存在 132 模式的子序列。

示例 2：

输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。

示例 3：

输入：nums = [-1,3,2,0]
输出：true
解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。

=====

算法思路:

根据题目要求，我们从右往左枚举数组，尝试找到题解中的元素i。由于是从右往左遍历，因此，j，k必然是从已经访问过的元素里寻找。如果能找到符合条件的j，k，那么我们就找到了一组解。让我们通过下面一步一步的推理来找出这道题的特征，从而写出高效的算法。为了方便描述我们假设一个数组为20个元素。此假设并不影响对这道题一般性特征的提取。

1.  首先，末尾元素nums[19]做为题解的nums[i]，是不可能的。排除它是i的可能，但它有可能是k，因此我们需要把它存下来。我们把它放入一个新数组stck中。为了做为未来nums[k]的候选。

2.  假设nums[18]到nums[10]数值依次递减。那么任何一个值都不可能是题解中的元素i。这个现象比较明显，此处不做证明。我们把它们依次放入stck中。stck最后一个值stck[-1]为nums[10]。python语言中，数组的索引-1表示倒数第一个，-2表示倒数第二个。以此类推。下面沿用此方式来进行描述。

3.  第一次升高在nums[9]处，即，nums[9]大于stck[-1](nums[10])或其他。此时它也不可能为nums[i]，因为它后面的元素在原数组中是递增的，不可能找到nums[j]>nums[k]。此时我们如何更新这个stck数组呢？

先给结论1: 我们在stck中删除所有小于nums[9]的元素。把小于nums[9]的最大元素，比如nums[12]存入另一个变量k_max中。然后nums[9]放入stck中。此时stck中为[19, 18,17,16,15,14,13,9], k_max=nums[12]

这里有两个点需要咱重点关注一下:

a. stck仍然保持一个递减的状态。

b. 基于原数组的顺序，k_max这个元素之前有个比它大的元素nums[9]。

这两点很重要。

接下来我们证明一下为什么可以这样做，并且不影响最后的结果。

假设元素nums[11]能成为题解的nums[k]，那么在nums[9]之前必然有个nums[i]小于nums[11]，那么nums[i]，nums[9]，k_max(即nums[12])也能成为一个题解。其他被删除的元素也是如此。所以删除它们，并不影响结果。

4.  让我们继续向左遍历，我们来到了nums[8]。此时会有两种情况:

a.  如果nums[8]大于stck[-1](值为nums[9])，按照结论1的方式操作stck和k_max值。即，删除stck中所有小于nums[8]的元素。把小于nums[8]的最大元素，如nums[15]，存入k_max中。然后nums[8]放入stck中。此时stck中为[19, 18,17,16,8], k_max=nums[15]。此操作也不会影响最终结果。此证明类似结论1的证明，这里咱在解释一遍，加深一遍印象。

假设nums[14]为题解中的nums[k]，在nums[8]之前的某个元素nums[i]可以和nums[14]构成一个题解，那么nums[i]也可以和nums[8]，nums[15]构成一个题解。因为nums[i]小于nuns[14]，而nums[14]又小于nums[15]。

b.  如果nums[8]小于stck[-1](值为nums[9])，，我们能放入数组吗？这里又出现两种情况: 如果它小于k_max。那此时我们已经找到了一个题解。如果大于k_max，那么就放入stck，做为候选。此时stck仍然保持一个递减的状态。

到此，我们基本就可以发现规律了。当我们继续向左遍历，仍然遵循第3，4点，维护stck和k_max变量。直到枚举完成。

我们再补充解释几个细节:

1.  对于上面提到的第2，3点，如果在放入1个元素后就出现升高，也是符合这个规律的。大家可以自行推导一下。

2. 变量k_max也有两个特征:

a.  按照原数组的顺序，它前面始终有一个比它大的元素。

b.  存入它的元素都比它的当前值大。

此算法的时间复杂度为O(n)。下面是代码实现:

class Solution(object):def find132pattern(self, nums):""":type nums: List[int]:rtype: bool"""stck=[nums[-1]]k_max=float("-inf")nums_len=len(nums)for i in range(nums_len - 2, -1, -1):while len(stck)>0 and nums[i]>stck[-1]:k_max=stck[-1]stck.pop()if nums[i] >= k_max:stck.append(nums[i])else:return Truereturn False    

这篇文章通过对一个具体实例的分析，一步一步的对这道算法题的单调栈的解法给大家做了较为深入的剖析。希望能对大家理解它背后的原理有所帮助。