**Solution**

**Next Greater Element I** https://leetcode.com/problems/next-greater-element-i/

**Algorithm**

- https://discuss.leetcode.com/topic/77916/java-10-lines-linear-time-complexity-o-n-with-explanation
- Suppose we have a decreasing sequence followed by a greater number. For example [5, 4, 3, 2, 1, 6] then the greater number 6 is the next greater element for all previous numbers in the sequence.
- We use a stack to keep a decreasing sub-sequence, whenever we see a number x greater than stack.peek() we pop all elements less than x and for all the popped ones, their next greater element is x.
- For example [9, 8, 7, 3, 2, 1, 6]. The stack will first contain [9, 8, 7, 3, 2, 1] and then we see 6 which is greater than 1 so we pop 1 2 3 whose next greater element should be 6.

```
class Solution(object):
def nextGreaterElement(self, findNums, nums):
"""
:type findNums: List[int]
:type nums: List[int]
:rtype: List[int]
"""
cache, st = {}, []
for x in nums:
if len(st) == 0:
st.append(x)
elif x <= st[-1]:
st.append(x)
else:
while st and st[-1] < x:
cache[st.pop()] = x
st.append(x)
result = []
for x in findNums:
if x in cache:
result.append(cache[x])
else:
result.append(-1)
return result
```

**Condensed Code**

```
class Solution(object):
def nextGreaterElement(self, findNums, nums):
"""
:type findNums: List[int]
:type nums: List[int]
:rtype: List[int]
"""
cache, st = {}, []
for x in nums:
while st and st[-1] < x:
cache[st.pop()] = x
st.append(x)
result = [-1]*len(findNums)
for idx,x in enumerate(findNums):
if x in cache:
result[idx] = cache[x]
return result
```