Mono-descreasing stack / normal order loop twice⌗

  • Loop twice to solve circular interger array
  • Mono-descreasing stack to store index, avoid HashMap in Next Greater Element I, as there is a cicular array.
class Solution {
public:
	vector<int> nextGreaterElements(vector<int>& nums) {
		vector<int> res(nums.size(), -1);
		stack<int> st;

		for (int j = 0, i = 0; j < nums.size() * 2; ++j) {
			i = j >= nums.size() ? j - nums.size() : j;
			while (!st.empty() && nums[st.top()] < nums[i]) {
				res[st.top()] = nums[i];
				st.pop();
			}
			st.push(i);
		}
		return res;
	}
};