<span>【题解】力扣 503. 下一个更大元素 II</span>
题目来源
思路
如果直接通过暴力求解的话，对于每一个元素都要去寻找比他更大的元素，时间复杂度将会变成 \(O(N^2)\) 。所以得想办法优化。
我们可以发现，如果数组的前半部分是单调不增的，那么就会由恨得的计算资源的浪费。比如说 [6,5,4,3,8] ，对于前面的 [6,5,4,3] 等数字都需要向后遍历，当寻找到元素8的时候才找到了比自己大的元素；而如果已知6向后找到的元素8才找到了比自己大的数字，那么对于元素 [5,4,3] 来说，它们都比元素6更小，所以它们的更大的元素一定是8，不需要再单独的对 [5,4,3] 分别再遍历一次！！
我们可以通过 单调栈 来实现。单调栈 就是指栈里面的元素从栈底到栈顶是 单调递增 或者 单调递减 的。
用一个新数组来存放答案结果
这个栈用来存放原数组的下标！！
- 如果栈为空，放下标入栈。
- 如果栈不为空
- 如果新的元素小于栈顶下标位置的元素，就将新的元素下标入栈；
- 如果新的元素大于栈顶下标位置的元素，则将栈顶的下标弹出，直到当前元素比栈顶元素小位置（在弹出栈顶下标的时候，可以利用一个和原数组相同大小的新数组，在相同下标的位置更新为新的元素）
遍历数组可以通过取模来遍历。
注意！！！新数组要初始化为-1，防止数组内的最大值老无所依！
class Solution {
public int[] nextGreaterElements(int[] nums) {
int len = nums.length;
int[] ret = new int[len];
Arrays.fill(ret, -1);
Deque<Integer> stack = new LinkedList<>(); // 记录的是下标
for(int i = 0;i<len*2-1;i++){
while(!stack.isEmpty() && nums[stack.getLast()] < nums[i%len]){
ret[stack.removeLast()] = nums[i%len];
}
stack.addLast(i%len);
}
return ret;
}
}
拓展
可以通过静态数组来模拟栈，这样代码可以更快一点
int ans = new int[n];
Arrays.fill(ans, -1);
int stack = new int[n*2];
int botten = 0, head = -1;
for(int i = 0;i<n*2-1;i++){
while(botten <= head && nums[i%n] > nums[stack[head]]){
int u = stack[head--]; // 取出栈顶元素的下标
ans[u] = nums[i%n];
}
stack[++head] = i%n; // 将下标加入到栈中
}
return ans;
