20210306 503. 下一个更大元素 II

题目

https://leetcode-cn.com/problems/next-greater-element-ii/

解法

暴力略(由于是循环数组,为了找循环的最大值,可以将原数组复制成2*nums.lenth长度的,或者i%nums.length)

单调栈

维护一个递减的单调栈,栈里面存放index,如果后边得数字比栈顶的大那么证明,遍历到的数字是第一个比栈顶nums[index]大的数值

public int[] nextGreaterElements(int[] nums) {
    int[] result = new int[nums.length];
    Arrays.fill(result, -1);
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < nums.length * 2; i++) {
        int num = nums[i % nums.length];
        while (!stack.isEmpty() && nums[stack.peek()] < num) {
            result[stack.pop()] = num;
        }
//只有比length小的index才可以入队列,保证length后边的数字只是遍历,不会影响栈里面的值
        if (i < nums.length) {
            stack.push(i);
        }
    }
    return result;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注