单调栈 02

单调栈

单调栈里存的是数组nums的下标，且栈是单调递增的。所以在遍历数组的过程中，要循环查看栈顶元素对应值是否小于当前值，若小于，则当前元素就是栈顶下标对应位置的“更大的数”，需要弹栈，然后给res赋值记录下来。最后让当前位置下标入栈即可。

这里有个细节，因为要找到整个数组的“更大的数”，即下一个数，所以需要遍历两遍数组。为了代码的统一性，所以循环 2 * n - 1次，下标采取 i % n 的方式达到循环不越界的效果。

代码如下：

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < 2 * n - 1; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                res[stack.pop()] = nums[i % n];
            }
            stack.push(i % n);
        }
        return res;
    }
}

测试代码，便于理解栈的变化

public class Solution {

    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < 2 * n - 1; i++) {
            System.out.println("i = " + i);
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                res[stack.pop()] = nums[i % n];
            }
            System.out.print("res[]: ");
            System.out.println(Arrays.toString(res));
            stack.push(i % n);
            System.out.print("stack: ");
            System.out.println(stack);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.nextGreaterElements(new int[]{1, 8, -1, -100, -2, -222, 1111111, -111111})));
    }

}

i = 0
res[]: [-1, -1, -1, -1, -1, -1, -1, -1]
stack: [0]
i = 1
res[]: [8, -1, -1, -1, -1, -1, -1, -1]
stack: [1]
i = 2
res[]: [8, -1, -1, -1, -1, -1, -1, -1]
stack: [2, 1]
i = 3
res[]: [8, -1, -1, -1, -1, -1, -1, -1]
stack: [3, 2, 1]
i = 4
res[]: [8, -1, -1, -2, -1, -1, -1, -1]
stack: [4, 2, 1]
i = 5
res[]: [8, -1, -1, -2, -1, -1, -1, -1]
stack: [5, 4, 2, 1]
i = 6
res[]: [8, 1111111, 1111111, -2, 1111111, 1111111, -1, -1]
stack: [6]
i = 7
res[]: [8, 1111111, 1111111, -2, 1111111, 1111111, -1, -1]
stack: [7, 6]
i = 8
res[]: [8, 1111111, 1111111, -2, 1111111, 1111111, -1, 1]
stack: [0, 6]
i = 9
res[]: [8, 1111111, 1111111, -2, 1111111, 1111111, -1, 1]
stack: [1, 6]
i = 10
res[]: [8, 1111111, 1111111, -2, 1111111, 1111111, -1, 1]
stack: [2, 1, 6]
i = 11
res[]: [8, 1111111, 1111111, -2, 1111111, 1111111, -1, 1]
stack: [3, 2, 1, 6]
i = 12
res[]: [8, 1111111, 1111111, -2, 1111111, 1111111, -1, 1]
stack: [4, 2, 1, 6]
i = 13
res[]: [8, 1111111, 1111111, -2, 1111111, 1111111, -1, 1]
stack: [5, 4, 2, 1, 6]
i = 14
res[]: [8, 1111111, 1111111, -2, 1111111, 1111111, -1, 1]
stack: [6, 6]
[8, 1111111, 1111111, -2, 1111111, 1111111, -1, 1]

Process finished with exit code 0