LeetCode

456. 132 Pattern

文章目录
  1. 1. 题目
  2. 2. 思路

题目


https://leetcode.com/problems/132-pattern/submissions/

思路

最开始我想速通这道题，就直接准备写三个循环把它遍历了，只要满足条件就算OK，于是我写下了如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def find132pattern(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) <=2:
            return False
        for i in range(len(nums)):
            for j in range(len(nums)):
                for k in range(len(nums)):
                    if i<j<k and nums[i]<nums[k]<nums[j]:
                        return True
        return False

然后leetcode直接给了我一个超长数组让我算超时了….

于是我只能发动仓鼠那贫瘠的大脑努力思考一下了：

先看复杂度，这种遍历法的时间复杂度是三次方，那尝试一下把复杂度降低一两个量级？也许可以通过固定好132模式中的1，然后来找3，再确定2的方式来解决。

行吧这个方法也不行。

那只能使用堆栈方式了（说实话我还不太能掌握堆栈），代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def find132pattern(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) <=2:
            return False
        third = float('-inf')
        stack = []
        for i in range(len(nums)-1, -1, -1):
            if nums[i] < third:
                return True
            else:
                while stack and stack[-1] < nums[i]:
                    third = stack.pop()
            stack.append(nums[i])
        return False