Leedcode 456. 132模式 Python实现

本文主要是介绍Leedcode 456. 132模式 Python实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

下面分析转自于：https://blog.csdn.net/nunuwode/article/details/81990426

2.挺巧妙的方法，从后往前遍历，将数字从大到小依次压栈，当遇到一个数比栈顶大的时候，依次弹栈，将弹出来的数赋给一个变量third，然后直到遇到栈顶的数比当前这个数大，就将这个数压栈。这样就保证了在遍历的过程中，栈里保存着最大的数，third保存着最大的数下的尽量大的数。只有third尽量的大，才能更容易找到比third小的数，也就是第一个数。

比如：1 2 3 10 7 8 9 6 5

一开始栈为空，third为INT_MIN，遇到5则压栈。

栈: 5 third:INT_MIN

遇到6弹栈 栈：6 third：5

遇到9弹栈 栈：9 third：6

遇到8压栈 栈：9 8 third 6

遇到7压栈 栈：9 8 7 third 6

遇到10 将10与依次弹栈的数对比，直到栈为空或者找到比10大的数，10才进栈。因而栈为：10 third：9

遇到3 < 9 则找到一个132结构 3 10 9 return true

在这个过程中，third始终能够保持在132中第二个最大的数后面第二大的数。

import sys
class Solution:def find132pattern(self, nums):""":type nums: List[int]:rtype: bool"""n = len(nums)if n < 3:return Falsestack = []third_nums = -sys.maxsizefor i in range(len(nums)):if nums[n -1 - i] < third_nums:return Truewhile (len(stack) >= 1) and (nums[n - 1 - i] > stack[-1]):third_nums = stack.pop(-1)stack.append(nums[n - 1 - i])return False

 

 

这篇关于Leedcode 456. 132模式 Python实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---