思路
最粗暴的方法就是O(n²)，这题也没卡暴力，可以击败5%混过去，但可以用单调栈来优化。
众所周知，单调栈致力于解决“寻找首个大于(小于)当前位置的值”，要明白单调栈的优势，就要搞清楚它的原理。
常规方法慢在挨个枚举，对每个元素都去一个个的找满足条件的值，那自然是慢的。如果说暴力的思路是“用每个值去找答案”，那单调栈的思路可以形象地理解为“让答案自己去找值”。
就本题而言，单调栈中存的是还没有找到答案的下标，他们自底向上严格上升。在遍历中，如果当前栈顶下标对应的值比nums[i]小，那么nums[i]就是当前值答案，将nums[i]计入ans中并弹出当前下标即完成一次操作。
这样做的正确性是显然地，因为有栈的后入先出特性做保证，当前nums[i]一定最有可能是栈顶元素的答案。
更具体地，因为这题是循环数组，所以需要遍历两次，初始化ans数组为全-1就可以避免最后再来为栈内未出栈的元素赋-1的操作。
代码
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
const int n = nums.size();
stack<int> stk;
vector<int> ans(n, -1);
stk.push(0);
for (int i = 0; i < n; i++) {
while(!stk.empty() && nums[stk.top()] < nums[i]) {
ans[stk.top()] = nums[i];
stk.pop();
}
stk.push(i);
}
for (int i = 0; i < n; i++) {
while(!stk.empty() && nums[stk.top()] < nums[i]) {
ans[stk.top()] = nums[i];
stk.pop();
}
stk.push(i);
}
return ans;
}
};