WillWang-X
8/17/2017 - 4:54 AM

## 456. 132 Pattern.py

``````# Time: O(n)
# Space: O(n)
# 456. 132 Pattern
'''
Packing information into names
'''

# version 1.0
class Solution(object):
def find132pattern(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
ak = float("-inf")
st = []
for i in reversed(xrange(len(nums))):
if nums[i] < ak:
return True
else:
while st and nums[i] > st[-1]:
ak = st.pop()
st.append(nums[i])

return False

# version 1.1
class Solution(object):
def find132pattern(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
real_2 = float("-inf")
potenial_2 = []
for i in reversed(xrange(len(nums))):
if nums[i] < real_2:
return True
else:
while potenial_2 and nums[i] > potenial_2[-1]:
real_2 = potenial_2.pop()
potenial_2.append(nums[i])

return False

# version 1.2
class Solution(object):
def find132pattern(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
cur_2 = float("-inf")
pool_2 = []
for i in reversed(xrange(len(nums))):
if nums[i] < cur_2:
return True
else:
while pool_2 and nums[i] > pool_2[-1]:
cur_2 = pool_2.pop()
pool_2.append(nums[i])

return False

# version 1.3
class Solution(object):
def find132pattern(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
max_2 = float("-inf")
pool_2 = []
for i in reversed(xrange(len(nums))):
if nums[i] < max_2:
return True
else:
while pool_2 and nums[i] > pool_2[-1]:
max_2 = pool_2.pop()
pool_2.append(nums[i])

return False

# version 1.4
``````