Next Greater Element
Given a circular array (which is represented as a regular array), find the next greater element for each element in the array. The next greater element of an element at index i is the first element to its right (in a circular manner) that is greater than the element at index i.
Constraints:
- The input array will have at least one element.
- The input array will have at most 1000 elements.
- All elements in the array will be integers.
Examples:
Input: [1, 2, 1]
Output: [2, -1, 2]
Explanation: For the first element (1), the next greater element is 2. For the second element (2), there is no greater element to its right, so the next greater element is -1. For the third element (1), the next greater element is 2, which is the first element in the array (circular manner).
Solutions
Stack
We use a stack to keep track of the indices of the elements in the array. We iterate over the array twice (to simulate the circular array). For each element, we pop all the elements from the stack that are smaller than the current element and update the result array with the current element as the next greater element. We then push the current index onto the stack.
def nextGreaterElements(nums):
n = len(nums); res = [-1] * n; stack = []; for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
res[stack.pop()] = nums[i % n]; stack.append(i % n); return resFollow-up:
What if the array is not circular?
