<p>Given a circular integer array <code>nums</code> (i.e., the next element of <code>nums[nums.length - 1]</code> is <code>nums[0]</code>), return <em>the <strong>next greater number</strong> for every element in</em> <code>nums</code>.</p>

<p>The <strong>next greater number</strong> of a number <code>x</code> is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn&#39;t exist, return <code>-1</code> for this number.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,1]
<strong>Output:</strong> [2,-1,2]
Explanation: The first 1&#39;s next greater number is 2; 
The number 2 can&#39;t find next greater number. 
The second 1&#39;s next greater number needs to search circularly, which is also 2.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,3]
<strong>Output:</strong> [2,3,4,-1,4]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>


# class Solution(object):
#     def nextGreaterElements(self, nums):
        

#         res = [-1] * len(nums)
#         stack = []
#         for i in range(len(nums) * 2):
#             idx = i % len(nums)
#             v = nums[idx]
#             while stack and stack[-1][0] < v:
#                 cur_value, cur_idx = stack.pop()
#                 res[cur_idx] = v
#             if i < len(nums):
#                 stack.append((v, i))

#         return res
class Solution(object):

    def nextGreaterElements(self, nums):
        #Circular array find the next greater element for every element in the nums 
        #Next greater elem of num x is the first num greater to the current element
        dec_stack = []
        res = [-1] * len(nums)
        
        #Find it normally L -> R
        for pos, num in enumerate(nums): 
            while dec_stack and num > dec_stack[-1][0]: 
                prev_num, prev_pos = dec_stack.pop()
                res[prev_pos] = num
            
            dec_stack.append((num, pos))
            
        #Find it R-> L to make it circular
        # [5,4,3,2,1]

        #You're emulating the circular array by doing it twice.         
        for pos, num in enumerate(nums): 
            while dec_stack and num > dec_stack[-1][0]:
                prev_num, prev_pos = dec_stack.pop()
                res[prev_pos] = num
            
            
        return res
# class Solution(object):
#     def nextGreaterElements(self, nums):
#         #Circular array find the next greater element for every element in the nums 
#         #Next greater elem of num x is the first num greater to the current element
#         dec_stack = []
#         res = [-1] * len(nums)
        
#         #Find it normally L -> R
#         for pos, num in enumerate(nums): 
#             while dec_stack and dec_stack[-1][0] < num: 
#                 prev_num, prev_pos = dec_stack.pop()
#                 res[prev_pos] = num
            
            
            
#             dec_stack.append((num, pos))
            
#         #Find it R-> L to make it circular
#         # [5,4,3,2,1]

#         #You're emulating the circular array by doing it twice.         
#         for pos, num in enumerate(nums): 
#             while dec_stack and dec_stack[-1][0] < num: 
#                 prev_num, prev_pos = dec_stack.pop()
#                 res[prev_pos] = num
            
            
#         return res


# class Solution(object):
#     def nextGreaterElements(self, nums):
#         #circular array so just do it twice 
#         inc_stack = []
#         result = [-1] * len(nums) 
# #This is done without a "circular array"
#         for pos, num in enumerate(nums):
#             while inc_stack and nums[inc_stack[-1]] < num: #This has a next greater element 
#                 smaller_stack_ele = inc_stack.pop()
#                 result[smaller_stack_ele] = num
            
#             inc_stack.append(pos)
        
# #Handling the circular array now 
#         for num in nums: 
#             while inc_stack and nums[inc_stack[-1]] < num: 
#                 smaller_stack_ele = inc_stack.pop()
#                 result[smaller_stack_ele] = num
#         return result 
#12/16/2020
# class Solution(object):
#     def nextGreaterElements(self, nums): 
#         #Circular Array for the next greater num 
#         #First solution is two loops then 
#         #First w/ our stack containing what we need and also that we only do it as a normal pass
#         #i.e non circular first
#         #Second pass the stacks will contain the next respective greater elements if possible 
#         stack = []
#         result = [-1] * len(nums)
#         for pos, num in enumerate(nums): 
#             while stack and nums[stack[-1]] < num: 
#                 prev_greater_ele = stack.pop()
#                 result[prev_greater_ele] = num 
#             #THIS STACK CONTAINS ALL THE POSITION of numbers 
#             stack.append(pos)
            
#         #Trying to find the remaining elements we care about with our circular array now 
#         #It's almost as if we have these numbers we couldn't find 
#         #So now we are going through it again almost as if extending the nums array with the same length (same nums)
#         for pos, num in enumerate(nums): 
#             while stack and nums[stack[-1]] < num: #monotonic decreasing 
#                 #This prev_greater position get's added with the number 
#                 prev_greater_ele = stack.pop()
#                 result[prev_greater_ele] = num 
                
#         return result 
            
            
            

'''
The idea here is to store the indexes of the elements that we haven't seen a greater than value for them yet
we do this because if you stored the values you wouldn't be able to easily know where a value is at so you
can set it accordingly. This comes in handy in the second loop.

The values in the stack when we enter the second loop will always be decending, this is an important part of knowing that meaning the number at the TOP will be the max so far 
we are setting the indexes to their correct value. Since we always will set the index's left in the stack to the smallest
number when reiterating over the stack, ensuring a correct answer. 
'''

# class Solution(object):
#     def nextGreaterElements(self, nums):
#         stack = []
#         result = [-1] * len(nums)
#         #get the first normal array i.e not circular 
#         for i in range(len(nums)):
#             while stack and nums[stack[-1]] < nums[i]:
#                 result[stack.pop()] = nums[i]
#             stack.append(i)

#         #At this stage you will have the stack with the biggest number to then check with your result
#         #Meaning the circularity is now added 
#         for i in range(len(nums)):
#             while stack and nums[stack[-1]] < nums[i]:
#                 result[stack.pop()] = nums[i]
                
#         return result
    

# class Solution(object):
#     def nextGreaterElements(self, nums):
#         n = len(nums)
#         ret = [-1] * n
#         stack = nums[::-1]
#         for i in range(n - 1, -1, -1):
#             while stack and stack[-1] <= nums[i]:
#                 stack.pop()
#             if stack:
#                 ret[i] = stack[-1]
#             stack.append(nums[i])
#         return ret
# class Solution:
#     def nextGreaterElements(self, nums: List[int]) -> List[int]:
#         #make a monotone increasing stack
        
#         stack = []
#         nums = nums
#         nxt_ele = collections.deque([])
#         #[1,2,1]
#         #[2,-1,2]
#         for pos, num in enumerate(nums): 
#             while stack and nums[stack[-1]] <= num: 
#                 prev_greater = stack.pop()
#                 nxt_ele.append(num)
                
#             else: 
#                 nxt_ele.append(-1)
                
#             stack.append(pos)
                
            
            
            
            
            
#         print(nxt_ele)
18700