给你一个整数数组 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) 的解决方案吗？
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
# le = len(nums)
# if le <3:
# return False
# numsi = nums[0]
# for j in range(1,le):
# for k in range(le-1,j,-1):
# if numsi < nums[k] < nums[j]:
# return True
# numsi = min(numsi,nums[j])
# return False
le = len(nums)
if le < 3:
return False
min_list = [nums[0]]
for i in range(1, len(nums)):
min_list.append(min(min_list[-1], nums[i]))
s = []
for j in range(le-1,-1,-1):
while s and s[-1] < nums[j]:
k = s.pop()
if k > min_list[j]:
return True
s.append(nums[j])
return False
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/127258.html