503. 下一个更大元素 II

一 题目：

二 思路：

其实和上题差不多，数组改循环之后，咱们来两次就行，第一次先找到正序右边比自己大的，第二次就再来一次，看看左边比自己大的，第二次就不用push数据了

三代码：

public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];

        //第一轮找到右边比自己大的数
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            //便利顺便初始化了
            if (res[i]==0){
                res[i]=-1;
            }

            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                res[stack.pop()] = nums[i];
            }
            stack.push(i);
        }

        //剩下的数组单调递减
        //第二轮找到没找到的里，左边比自己大的数
        for (int i = 0; i < nums.length; i++) {
            //如果当前数大于栈内元素直接弹
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                res[stack.pop()] = nums[i];
            }
        }

        return res;
    }

剪枝的话可以第二个for循环条件里
for (int i = 0; i < nums.length; i++) 改成for (int i = 0; i < nums.length&&!stack.isEmpty()&&i<stack.peek(); i++)

意为：只看当前元素左边的数据，如果当前下标已经大于栈内元素了，就不用继续看了。