参考

思路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;}
};