参考

思路1: 暴力解法

思路2: 单调栈
使用场合: 寻找任一个元素的右边或者左边第一个比自己大或者小的元素位置, 存放的是遍历过的元素

记忆:
单调栈是对遍历过的元素做记录, 一般是对栈顶的元素 nums[mystack.top()] 做赋值操作的
如果想找到右边的元素大于左边, 则需要大的元素沉底 (如 7 3 5 9 1, 7的结果是9)
单调栈存储的是索引号

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> mystack;
        vector<int> res(temperatures.size());
        mystack.push(0);
        for (int i = 1; i < temperatures.size(); i++) {
            while (mystack.empty() != true && temperatures[i] > temperatures[mystack.top()]) {
                res[mystack.top()] = i - mystack.top();
                mystack.pop();
            }
            mystack.push(i);
        }
        return res;
    }
};

使用map映射索引号

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> mymap;
        for (int i = 0; i < nums1.size(); i++) {
            mymap[nums1[i]] = i;
        }

        stack<int> mystack;
        vector<int> res(nums1.size(), -1);
        mystack.push(0);
        for (int i = 1; i < nums2.size(); i++) {
            if (nums2[mystack.top()] >= nums2[i]) {
                mystack.push(i);//大的沉底
            } else {
                while (!mystack.empty() && nums2[mystack.top()] < nums2[i]) {
                    if (mymap.find(nums2[mystack.top()]) != mymap.end()) {
                        int index = mymap[nums2[mystack.top()]];
                        res[index] = nums2[i];
                    }              
                    mystack.pop();      
                }
                mystack.push(i);
            }            
        }
        return res;
    }
};

环形数组的处理方式: 1.nums拼接 2.遍历nums.size() * 2

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> res(nums.size(), -1);
        stack<int> mystack;
        mystack.push(0);
        for (int i = 1; i < 2 * nums.size(); i++) {
            if (nums[i % nums.size()] <= nums[mystack.top() % nums.size()]) {
                mystack.push(i);
            } else {
                while (!mystack.empty() && nums[i % nums.size()] > nums[mystack.top() % nums.size()]) {
                    res[mystack.top() % nums.size()] = nums[i % nums.size()];
                    mystack.pop();
                }
                mystack.push(i);
            }
        }
        return res;
    }
};