🚀 Elegant Python3 Solution | Monotonic Stack | Beats 99.41% 🔥
IntuitionTo solve the problem, we need to find the next greater element for each number in the circular array. A monotonic stack is ideal for this task, as it a
[![image.png](https://assets.leetcode.com/users/images/c10f3677-bd7b-41c3-bde3-95446a23e79c_1736098565.6313734.png)](https://leetcode.com/problems/next-greater-element-ii/submissions/1498746841/)


# Intuition
To solve the problem, we need to find the next greater element for each number in the circular array. A **monotonic stack** is ideal for this task, as it allows us to efficiently track the next greater elements while iterating. By traversing the array twice (to simulate its circular nature), we can ensure all elements are covered.

---

# Approach
1. **Simulate Circular Array**:
   - To handle the circular nature of the array, iterate over it twice using `i % len(nums)` to access elements.
2. **Use a Monotonic Stack**:
   - Maintain a stack to store elements in decreasing order. This helps efficiently find the next greater element.
   - As we traverse, pop elements from the stack that are smaller than or equal to the current element because they can’t be the next greater element.
3. **Result Array**:
   - Initialize a result array `res` with `-1` to represent elements with no next greater value.
   - Update `res[i]` with the top of the stack when the next greater element is found.
4. **Push to Stack**:
   - Add the current element to the stack for future comparisons.

---

# Complexity
- **Time complexity**:  
  $$O(n)$$  
  Each element is pushed and popped from the stack at most once, where \(n\) is the length of the array.

- **Space complexity**:  
  $$O(n)$$  
  The stack may store up to \(n\) elements in the worst case.

---

# Code
```python
class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [-1] * n  # Initialize the result array with -1
        stack = []      # Monotonic stack to track next greater elements
        
        # Iterate through the array twice to simulate circularity
        for i in range(2 * n - 1, -1, -1):
            num = nums[i % n]  # Current element (handle circular index)
            
            # Remove elements from the stack that are <= the current element
            while stack and stack[-1] <= num:
                stack.pop()
            
            # If the stack is not empty, the top of the stack is the next greater element
            if stack:
                res[i % n] = stack[-1]
            
            # Push the current element onto the stack
            stack.append(num)
        
        return res
```
![image.png](https://assets.leetcode.com/users/images/4af6434b-9fee-450c-8924-174c215db3b6_1736098656.9703357.png)
['Array', 'Stack', 'Monotonic Stack', 'Python', 'Python3']