#include "s0503_next_greater_element_ii.hpp"

// 循环数组首先考虑到的方法就是将两个数组拼接到一起处理。
// 我们将两个数组拼接到一起，然后用单调栈即可，但这样做有些浪费内存。
// 另一种处理方式是这样遍历：
// for (int i{0}; i < 2 * len; ++i) {
//   nums[i % len] ...
// }

vector<int> S0503::nextGreaterElements(vector<int>& nums) {
  int len = nums.size();
  if (len == 0) {
    return vector<int> {};
  } else if (len == 1) {
    return vector<int> {-1};
  }
  vector<int> ans(len, -1);
  stack<int> s;
  for (int i{0}; i < 2 * len; ++i) {
    if (s.empty()) {
      s.push(i);
      continue;
    }
    while (nums[i % len] > nums[s.top() % len]) {
      if (ans[s.top() % len] == -1) {
        ans[s.top() % len] = nums[i % len];
      }
      s.pop();
      if (s.empty()) {
        break;
      }
    }
    s.push(i);
  }
  return ans;
}