【单调栈】503. 下一个更大元素 II

503. 下一个更大元素 II

解题思路

• 参考496. 下一个更大元素 I

• 首先计算nums2的每一个元素的下一个比他大的元素，使用单调栈

• 将上面的结果和nums2中的每一个元素组成映射map

• 针对每一个Nums1的元素 查询map 记录map 的value

• 但是这个是循环的数组元素

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        // 使用单调栈计算  改造算法   只不过数组元素可以循环
        int n = nums.length;

        // 存放答案的数组
        int[] res = new int[n];
        Stack<Integer> s = new Stack<>();

        for(int i =2 * n - 1; i >= 0; i--){
            // 判断各自高矮
            while(!s.isEmpty() && s.peek() <= nums[i % n]){
                s.pop();
            }

            // 存放比当前元素大的元素
            res[i % n] = s.isEmpty()? -1:s.peek();
            s.push(nums[i % n]);
        }

        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25