Next Greater Element II

================================

Problem Statement

In this problem, we are given an integer array

that represents the heights of bars in a bar chart. We are asked to find the next greater element for each element in the array, considering the fact that the given array is wrapped around to the start of the array after reaching the end. This wrapping operation means that the next greater element of the last element in the array is the first element, the next greater element of the second last element is the second element, and so on.

Rules and Constraints

• The input array
  nums
  has a length of
  n
  and contains integers in the range of
  [1, n*10]
  .
• You can assume that for any two elements in the array, their values are unique.
• The expected time complexity is O(n), and the expected space complexity is O(n).
• The input array may contain repeated elements.

Output

The solution should return an array of integers, where each integer is the next greater element for the corresponding element in the input array

. If an element has no next greater element, the corresponding output should be an integer , indicating the absence of a next greater element.

This problem requires careful consideration of the wrapping behavior and careful planning of the algorithm to achieve an O(n) time complexity.

Example

Input: {"nums":[1,2,1]} Output: [2,-1,2]