题目来源

503. 下一个更大元素 II

思路

如果直接通过暴力求解的话,对于每一个元素都要去寻找比他更大的元素,时间复杂度将会变成 \(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;

题解来源

  1. 负雪明烛
  2. 宫水三叶