503. 下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 _ nums 中每个元素的 下一个更大元素_ 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

提示:

• 1 <= nums.length <= 104
• -109 <= nums[i] <= 109

思路
本体采用 单调栈 的思路求解。详见视频

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* nextGreaterElements(int* nums, int numsSize, int* returnSize) {
    if (numsSize == 0)
        return NULL;
    int* res = (int*)malloc(numsSize * sizeof(int));
    memset(res, -1, sizeof(int) * numsSize);
    int stk[numsSize * 2 - 1], top = 0;
    for (int i = numsSize * 2 - 1; i >= 0; i--) {
        int x = nums[i % numsSize];
        while (top && x >= stk[top - 1]) {
            top--;
        }
        if (top && i < numsSize) {
            res[i] = stk[top - 1];
        }
        stk[top++] = x;
    }
    *returnSize = numsSize;
    return res;
}```