動機
久違的leetcode
Problem
Given an array of n
integers nums
, a 132 pattern is a subsequence of three integers nums[i]
, nums[j]
and nums[k]
such that i < j < k
and nums[i] < nums[k] < nums[j]
.
Return true
if there is a 132 pattern in nums
, otherwise, return false
.
Example 1:
Input: nums = [1,2,3,4]Output: falseExplanation: There is no 132 pattern in the sequence.
Example 2:
Input: nums = [3,1,4,2]Output: trueExplanation: There is a 132 pattern in the sequence: [1, 4, 2].
Example 3:
Input: nums = [-1,3,2,0]Output: trueExplanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
Constraints:
n == nums.length
1 <= n <= 2 * 105
-109 <= nums[i] <= 109
Sol
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
stk = []
mid = float('-inf')
for n in reversed(nums):
if n < mid and stk:
return True
while stk and stk[-1] < n:
mid = max(mid,stk.pop())
stk += n,
return False