Untitled

mail@pastecode.io avatar
unknown
python
2 years ago
715 B
1
Indexable
Never
#consider [3,5,2,4,6,8], 
#working backward 8,6,4,2 decreasing, cannot be the max number, put in stack=[8,6,4,2]
#at 5, it may be a max, find the largest_but_smaller_than_max by poping from stack which is 4
# stack is [8,6,5] now which should always be decreasing
#if we get another number 3<4, done
import math
def sol(input):
    stack = []
    largest_but_smaller_than_max = -math.inf
    for num in input[::-1]:
        if num < largest_but_smaller_than_max: #num is goal
            return True
        while stack and num>stack[-1]: #when num is a possible max, 
            largest_but_smaller_than_max=max(largest_but_smaller_than_max,stack.pop())
        stack.append(num)
    return False