1.题目描述
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:
输入: [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2； 数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
注意: 输入数组的长度不会超过 10000。
2.解法一：暴力法
思路：对于nums中每个元素，直接遍历两遍，确定下一个更大的数存在与否。
代码：运行时间296 ms
class Solution { public: vector<int> nextGreaterElements(vector<int>& nums) { int n = nums.size(); if(n==0) return {}; vector<int> res(n,-1); for(int i=0; i<n; ++i){ //下一个更大的数 for(int j=i+1; j<2*n; ++j){ int num2 = nums[j%n]; if(nums[i] < num2){ res[i]=num2; break;} } } return res; } };
3.解法二：翻倍数组，避免循环（栈）
思路：将原nums数组增长一倍，把nums完整拷贝到增长的区间。因为只需要遍历数组两遍，一定可以确定nums中的每一个元素的下一个更大的数，存在或不存在。
代码：运行时间 144ms
class Solution { public: vector<int> nextGreaterElements(vector<int>& nums) { //小技巧：增大一倍数组，不用考虑循环 for(int num : nums){ doubleNums.push_back(num); } for(int num : nums){ doubleNums.push_back(num); } int sz = nums.size(); vector<int> res(sz,-1);//sz在运行时才有正确值，所以这两个定义放在函数内部 for(int i=0; i<2*sz ; ++i){ while(!st.empty() && nums[st.top()]<doubleNums[i]){ res[st.top()]=doubleNums[i]; st.pop(); } if(i<sz) st.push(i);//只需要原nums中的数字所处位置的【下标】进栈
//因为res的长度必须是sz，超过sz的部分我们只是为了给之前栈中的数字找较大值，所以不能压入栈
} return res; } private: vector<int> doubleNums; stack<int> st; };
4.解法三：取模运算，循环遍历（栈）
思路：基本同理于解法一，数组需要遍历两次（循环遍历），才能确定每一个元素的下一个更大的数字是否存在。这里的改进在于：无需把nums增长一倍并拷贝，而是通过取模运算（ i = i % sz），使得遍历的下标 i 不越界。显然，这样更简单。
代码：运行时间96ms
class Solution { public: vector<int> nextGreaterElements(vector<int>& nums) { int n = nums.size(); vector<int> res(n, -1);//技巧：提前都初始化为-1，减少后面重新赋值的步骤 for (int i = 0; i < 2 * n; ++i) { int num = nums[i % n]; while (!st.empty() && nums[st.top()] < num) { res[st.top()] = num; st.pop(); } if (i < n) st.push(i);//下标进栈 } return res; } private: stack<int> st; };
5.解法四：启发性思路，定义struct元素入栈比较
思路：
- 定义struct Item { int index; int v;} ，为的就是协调对应数组元素值与数组下标的关系，便于比较。
- 上面的解法二和三中的采用的是下标进栈，达到和这里使用struct一样的效果。
代码：运行时间148ms
struct Item { int index; int v; }; class Solution { public: vector<int> nextGreaterElements(vector<int>& nums) { int n=nums.size(); if(n==0) return {}; vector<int> res(n,-1); stack<Item> s; Item t; t.index=0; t.v=nums[0]; s.push(t);
//遍历第一次 for(int i=1;i<n;++i) { while(!s.empty() && nums[i]>(s.top()).v) { res[(s.top()).index]=nums[i]; s.pop(); } t.index=i; t.v=nums[i]; s.push(t); }
//遍历第二次 for(int i=0;i<n;++i) { if(s.empty()) break; while(!s.empty() && nums[i]>(s.top()).v) { res[(s.top()).index]=nums[i]; s.pop(); } } return res; } };
参考资料：