题目：132模式

给定一个整数序列：a1, a2, ..., an，一个132模式的子序列ai, aj, ak被定义为：当 i < j < k时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。 - 注意：n 的值小于15000。

示例1:
输入: [1, 2, 3, 4]
输出: False
解释: 序列中不存在132模式的子序列。
示例 2:
输入: [3, 1, 4, 2]
输出: True
解释: 序列中有 1 个132模式的子序列： [1, 4, 2].
示例 3:
输入: [-1, 3, 2, 0]
输出: True
解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].

来源：力扣（LeetCode）第456题

链接：https://leetcode-cn.com/problems/132-pattern

分析：

  • 还是单调栈，不过还需要用到另一个方法，逆向工作法。反向遍历列表就会发现不一样的做法。
  • 根据题意1代表最小元素，3代表最大元素，2代表次大元素
  • 通过单调递减栈找到最大元素的最大次大元素，然后再确定最小元素要比最大次大元素小。

思路：

  • 反向遍历列表。
  • 严格维护一个单调递减栈。
  • 一旦遇到一个大的元素，将栈内元素出栈，维护单调递减。入栈后，将自己作为题目中的最大元素，即中间的元素。
  • 将最后一个出栈的元素作为次大元素，即右边的元素。
  • 这样的好处是我找到的次大元素一定是与当前最大元素的值最近的，而且还在最大元素的后面。
  • 这样我只要在前面找到一个比次大元素小的值，也就是最小值，那么就是True。
  • 如果找不到，那么可能有两种情况。
    • 第一种在最大元素和次大元素之间，最小值比最大的次大元素还要大，不符合题意。但是要维护单调递减栈，所以入栈。
    • 第二种在最大元素之上，那么用刚才的方法重新确定最大元素和次大元素。由于它在最大元素之上，当它为最大元素时它能包括之前的最大元素在内，重新确定的次大元素一定会比之前的次大元素大。
  • 如果遍历完为止都没有返回True，那么返回False。

上代码：

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stack = []
        _min = float('-inf')
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] < _min:
                return True
            while stack and stack[-1] < nums[i]:
                _min = stack.pop()
            stack.append(nums[i])
        return False

复杂度分析：

  • 时间复杂度：O(n) n为列表的长度
  • 空间复杂度：O(n)

总结：

  • 逆向工作法，如果你想不出来细节时可以考虑使用。
  • 我一开始的思路是正向遍历，维护一个单调递减栈。
  • 然后确定一个最小值，但是次大元素在右边，所以单调栈内无法找到次大元素。如果次大元素在左边的话，就可以直接正向单调递减了。