Python Three Pass


  • 0

    Pass One, get minSofar[i] for i in range 0 - len(nums), minSofar[i] means the mininum element among all the elements on the left side of nums[i].

    Pass Two, get maxToend[i] for i in range len(nums) - 0, maxToend[i] means the largest element that appears on the right side of nums[i] that smalller that nums[i], if there isn't, then make it super large.

    Pass Three, find some i that minSofar[i] < maxToend[i] < nums[i], if it does, then return True

    Finally return False

    class Solution(object):
        def find132pattern(self, nums):
            minSofar, maxToend, stack = {}, {}, []
            m = 0xffffffff
            for i in xrange(len(nums)):
                m = min(nums[i], m)
                minSofar[i] = m
            for i in xrange(len(nums) - 1, -1, -1):
                tmp = 0xffffffff
                while stack and stack[-1] < nums[i]:
                    tmp = stack.pop()
                stack.append(nums[i])
                maxToend[i] = tmp
            for i in xrange(len(nums)):
                if minSofar[i] < maxToend[i] < nums[i]:
                    return True
            return False
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.