题目分析

题目非常有趣，而且题意清晰，考察单调栈的思路，单调栈的题目时间复杂度往往是**$O(n)$**量级，小伙伴们先思考应该如何求解，如果不是$O(n)$的时间复杂度，再去想一想如何优化。

暴力法

我们先分析这个题目，要求是132模式，因此对于$a_i, a_j, a_k, \ i < j < k$来说，$a_i$应当越小越好，所以若$a_i$满足条件，则取前j个数的最小值一定也满足条件。

首先我们记录最小的前缀，然后我们遍历所有的元素，将每一个元素作为$a_j$，然后寻找在j索引之后，小于$a_j$的最大值$a_k$即可。若找到$a_k$大于$a_i$则返回True，如果遍历所有元素都没有找到则返回False。

算法的**时间复杂度为$O(n^2)$，空间复杂度为$O(n)$**。

class Solution(object):
    def find132pattern(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        mini = [nums[0]]
        for x in nums[1:]:
            mini.append(min(mini[-1], x))
        for j in range(1, len(nums) - 1):
            if nums[j] > mini[j]:
                maxi = -float('inf')
                for k in range(j + 1, len(nums)):
                    if maxi < nums[k] < nums[j]:
                        maxi = nums[k]
                if maxi > mini[j]:
                    return True
        return False

单调栈

单调栈的思路是维护一个单调递减的栈，栈内元素的含义是，当前元素之后的备选方案，是132模式中的2，最小前缀的含义是当前元素之前的备选方案，是132模式中的1。

如果栈顶元素小于等于最小前缀，说明$a_k$较小，应当弹出，当某个元素$a_k$大于最小前缀时，说明满足了$a_k > a_i$的条件，再判断$a_k$和$a_j$的大小关系即可。如果$a_k < a_j$则找到了符合132模式的序列，返回True，如果遍历所有的j都没有找到，则返回False。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

class Solution(object):
    def find132pattern(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        mini, stack = [nums[0]], []
        for x in nums[1:]:
            mini.append(min(mini[-1], x))
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] > mini[i]:
                while stack and stack[-1] <= mini[i]:
                    stack.pop()
                if stack and stack[-1] < nums[i]:
                    return True
                stack.append(nums[i])
        return False

刷题总结

对于数组题目来说，有一些常用的算法，如单调栈，单调队列，二分查找，动态规划等等，小伙伴们一定要多多练手，才能迅速求解。