Leetcode: 132-Pattern

Given a sequence of n integers a1, a2, ..., an,
a 132 pattern is a subsequence ai, aj, ak such that i < j < k and
ai < ak < aj. Design an algorithm that takes a list of n numbers as
input and checks whether there is a 132 pattern in the list.
Note: n will be less than 15,000.

Example 1:
Input: [1, 2, 3, 4]
Output: False
Explanation: There is no 132 pattern in the sequence.

Example 2:
Input: [3, 1, 4, 2]
Output: True
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:
Input: [-1, 3, 2, 0]
Output: True
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

1. 询问

因为是LeetCode，题目描述得相当清晰，所以无需再问。

2. 分析

首先可以一眼看出来O(n^3)的暴力破解方法，即找出所有三元元组，然后判断是否符合条件。
然后这个题很容易让人想到Kadane算法。在O（n）时间内，可以得到min和max的subarray数组，但是这道理并不是单纯的min或者max关系，而是有两个大小关系，所以说Kadane这里并不适用。

正序遍历

一个很自然的想法是维持一个二元元组，然后遍历数组，尝试往里面填入和替换数值，等到符合条件的组合出现，或者遍历结束。假设元组为(a, b)，且a<b。
假如遇到新值c，等于的情况就略过了，而如果a<c<b的话就返回True，其次还有两种情况：

1. c>b：这种情况还是比较好判断，用c替换b即可。
2. c<a：这个就挺麻烦。因为我们希望a尽可能小，而b尽可能大。此时如果替换掉a，那么b也要放弃掉，因为b在c前面。由于不知道后面的情况，很难判断。例如，两个序列24142与24134，当持有24时，遇到1怎么办？一个该换一个不该换。

一个更进一步的尝试，是把b换成一个列表。毕竟132可以看成12两个端点范围内包含3.
b里面还是要放在a之后而且比a大的值。然而仔细想想，这里好像并没有什么用。因为c<a的情况其实和b关系不大。
因此正序遍历，很接近，但有一个关键地方无法处理。

逆序遍历

这个题tricky的地方就在这里，很微妙地，逆序和正序不一样。
假设维持二元元组(b,c)，遇到新值a，考虑如下两种情况：

1. a > b：用a替换b，b替换c。
2. c < a < b：这个就是逆序遍历遇到的问题，对应正序遍历的问题。不过，与正序遍历不同的是，a此时和bc都有关系。

因此假如把b换成线性列表呢？
那么b里面储存的元素应该都是比c大的。
现在再来 c < a < b的情况。a比c大，也要进b。同时我们希望c也尽可能地大。
因此b最好是元素从小到大排的栈，这样当a进栈时可以把所有更小的元素都pop出来，而且都赋给c，这样c得到最后一个pop的值，也就是仅次于a的值。
为了验证，类似于正序的两个例子，我们来看一下35453与2453，前者要4，后者不要4.
模拟两个例子的过程：

• 35453
  从b=[5], c=3开始
  a=4，进栈，b=[5, 4], c=3
  a=5，进栈，4被pop出来给c，因为要求c<b因此不继续pop5，那么b=[5,5],c=4
  a=3找到符合条件的值

• 2453
  从b=[5], c=3开始
  a=4，进栈，b=[5, 4], c=3
  a=2找到符合条件的值

可见这个算法可以解决二元元组的问题。时间复杂度O（n），空间复杂度O（n）。

3. 代码

class Solution:
    def find132pattern(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        ak = float("-inf")
        st = []
        for i in reversed(xrange(len(nums))):
            if nums[i] < ak:
                return True
            else:
                while st and nums[i] > st[-1]:
                    ak = st.pop()
            st.append(nums[i])
        return False

4. 总结

很巧妙的一道题。难度medium~hard。