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==) return {};
vector<int> res(n,-);
for(int i=; i<n; ++i){
//下一个更大的数
for(int j=i+; j<*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,-);//sz在运行时才有正确值，所以这两个定义放在函数内部
for(int i=; i<*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，减少后面重新赋值的步骤
for (int i = ; i < * 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==) return {};
vector<int> res(n,-);
stack<Item> s;
Item t;
t.index=;
t.v=nums[];
s.push(t);
//遍历第一次
for(int i=;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=;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;
}
};
参考资料：