[456][中等][栈] 132模式

题目描述

456. 132 模式

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

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

进阶：很容易想到时间复杂度为 O(n^2) 的解决方案，你可以设计一个时间复杂度为 O(n logn) 或 O(n) 的解决方案吗？

示例 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] 。

提示：

• n == nums.length

• 1 <= n <= 104

• -109 <= nums[i] <= 109

解题思路

注意到132模式中, 3是其中最大的数字, 且2还要比1大. 本题的关键, 是以3为划分点, 在左侧和右侧分别找出合适的1和2.

如果从左向右遍历, 记录维护3的位置, 如果使用当前位置左侧的最大值作为3, 数组中的132模式很可能出现在后面, 如[0, 4, -3, -1, -2], 如果以元素4为132模式中的3, 就无法找到正确的132子序列[-3, -1, -2].

换句话说, 1和3作为132模式中的最小值和最大值, 如果维护这两个值, 只会让他们之间的空间越来越大, 而真正的132模型在这个空间中出现的概率就越来越大.

所以有效的做法是维护2, 因为2是1和3之间的中间值, 如果1<2并且2<3, 根据传递性得到1<3. 我们从右向左遍历, 遇到的每一个元素, 都可能是最后的2, 即2的候选元素. 在它们遇到一个更大的元素后, 才能成为真正的2.

首先将最右侧的元素作为2的候选元素, 压入栈中. 在遍历下一个元素时, 如果新元素更小, 栈中的元素是没有资格成为真正的2的, 这个元素也要压入到栈中, 成为候选. 换个角度, 遇到一个新元素, 栈中所有小于这个元素的2的候选元素, 都具备了称为真正2的资格, 我们将栈顶所有小于新元素的元素弹出, 这些被弹出的元素都是可以真正作为2的. 我们再使用一个变量max_second, 记录所有被弹出元素的最大值, 这样有:

• 我们维护了一个2的候选元素栈, 且这个栈是单调递减栈, 因为更小的值被直接压入栈, 更大的值需要弹出比它小的值才会被压入栈

• 真正称为真正2的元素都被弹出, 栈中存在的值只是候选, 因为它们的左侧没有大于它们的值

• 我们只使用一个变量, 记录真正的2, 且只记录最大值. 无需记录3, 因为每个被弹出的值, 具有了真正是2的资格后, 就不再需要它对应的3了, 只需要寻找它对应的1即可

• 只记录真正的2的最大值, 是因为2越大, 留给1的空间就越大

因此, 继续遍历:

• 如果新元素小于max_second, 而max_second是具有2资格的元素, 肯定存在一个比它大的3, 因此我们就找到了一个结果, 直接返回True

• 对于新元素, 将其与栈顶元素比较, 如果它严格大于栈顶元素, 将栈顶元素弹出, 并将弹出的元素与max_second比较, 记录最大的具有2资格的元素. 重复这个过程直到栈为空, 或新元素不再大于栈顶元素, 将新元素压入栈

• 有个优化点, 如果新元素小于max_second, 它弹出的元素肯定也不会大于当前的max_second. 而如果我们还把这个元素压入栈, 后面被弹出时也不会对max_second产生影响, 因此这个新元素没有必要被压入栈中

最后代码如下:

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 3:
            return False

        stack = [nums[-1]]
        max_second = float('-inf')

        for i in range(n - 2, -1, -1):
            if nums[i] < max_second:
                return True

            while stack and nums[i] > stack[-1]:
                max_second = max(stack.pop(), max_second)

            if nums[i] > max_second:
                stack.append(nums[i])

        return False

参考资料

• 132模式
• 栈解法 超详细题解
• 【相信科学系列】详解为何使用「单调栈」来找最大的 K 是正确的 ...