Untitled
unknown
python
3 years ago
715 B
3
Indexable
#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
Editor is loading...