各位题友大家好！今天是 @负雪明烛 坚持日更的第 59 天。今天力扣上的每日一题是「456. 132模式」。

解题思路

今天这个题目很有意思，个人认为难度在中上。题目的 n 的范围是 15000，但是我测试了 $O(N^2)$ 复杂度的代码也不会超时。

题目要找 132 模式的组合，也就是对于 $i < j < k$ 有 $nums[i] < nums[k] < nums[j]$。下面我写了两种方法，方法一比较暴力，方法二性能比较高。

我选择的方法是维护 132模式中间的那个数字 3，因为 3 在 132 的中间的数字也是最大的数字。我们的思路是个贪心的方法：我们要维护的 1 是 3 左边的最小的数字；2 是 3 右边的介于 1 和 3 之间的数字。

方法一：使用暴力维护 3

这个方法就是 $O(N^2)$ 的解法，是这个题的暴力解法。

从左到右遍历一次，遍历的数字是 nums[j] 也就是 132 模式中的 3。根据上面的贪心思想分析，我们想让 1 是 3 左边最小的元素，然后使用暴力在 $nums[j+1 .. N-1]$ 中找到 132 模式中的 2 就行。

这个思路比较简单，也能 AC。

class Solution(object):
    def find132pattern(self, nums):
        N = len(nums)
        numsi = nums[0]
        for j in range(1, N):
            for k in range(N - 1, j, -1):
                if numsi < nums[k] and nums[k] < nums[j]:
                    return True
            numsi = min(numsi, nums[j])
        return False

时间复杂度：$O(N^2)$
空间复杂度：$O(1)$

方法二：使用单调栈维护 3

如果我们维护的是 132 模式中的 3，那么就希望 1 尽可能小，2 尽可能大。

所以思路是这样的：

遍历的位置 j 相当于 132 模式中的 3，即 nums[j] ；
2. 找到 3 左边的最小元素 为 1，即 nums[i] ；
3. 找到 3 右边比 3 小的最大元素 为 2，即 nums[k] ；

在方法一的做法中，是使用暴力求解得到的 2，很显然时间复杂度比较高。我们想要的 2 其实满足两个条件：

比 3 小；
在 $nums[j+1 .. N-1]$ 区间的最大元素。

为了找到这样的元素，我们可以使用一个单调递减的「栈」。所谓「单调栈」就是栈中的元素都是依次递增或者递减的，从而方便我们能维护好数组的一个区间内的「最大值」「次大值」等等。

想要求「次大值」，则需要一个单调递减的栈。这样的话，最大元素在栈底，次大元素在栈底的第二元素……假如用的是单调递增的栈，那么最大元素在栈顶，比它更小的元素到了之后，则需要插入栈的中间位置，很明显不合理。

具体到本题的实现方式：

求任何位置的左边最小的元素 nums[i] ，可以提前遍历一次而得到；
使用「单调递减栈」，把 nums[j] 入栈时，需要把栈里面比它小的元素全都 pop 出来，由于越往栈底越大，所以 pop 出的最后一个元素，就是比 3 小的最大元素 nums[k] 。
判断如果 nums[i] < nums[k] ，那就说明得到了一个 132 模式。

因为单调栈是建立在 3 的右边的，因此，我们使用从右向左遍历。

class Solution(object):
    def find132pattern(self, nums):
        N = len(nums)
        leftMin = [float("inf")] * N
        for i in range(1, N):
            leftMin[i] = min(leftMin[i - 1], nums[i - 1])
        stack = []
        for j in range(N - 1, -1, -1):
            numsk = float("-inf")
            while stack and stack[-1] < nums[j]:
                numsk = stack.pop()
            if leftMin[j] < numsk:
                return True
            stack.append(nums[j])
        return False

时间复杂度：$O(N)$
空间复杂度：$O(N)$

刷题心得

今天的单调栈的使用还是有点技巧的，当我们遍历到一个位置 $i$ 需要寻找数组中左边或者右边的所有数字和 $nums[i]$ 的大小关系的题目，可以考虑一下单调栈。

参考资料：

OK，以上就是 @负雪明烛写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！

算法每日一题题解

【每日一题】【负雪明烛】456. 132模式

解题思路

方法一：使用暴力维护 3

方法二：使用单调栈维护 3

刷题心得