LeetCode:2454. 下一个更大元素 IV(单调栈 & 优先级队列 Java)

2023-12-14 00:14:54

目录

2454. 下一个更大元素 IV

题目描述:

实现代码与解析:

单调栈 & 优先级队列

原理思路:


2454. 下一个更大元素 IV

题目描述:

????????给你一个下标从?0?开始的非负整数数组?nums?。对于?nums?中每一个整数,你必须找到对应元素的?第二大?整数。

如果?nums[j]?满足以下条件,那么我们称它为?nums[i]?的?第二大?整数:

  • j > i
  • nums[j] > nums[i]
  • 恰好存在?一个?k?满足?i < k < j?且?nums[k] > nums[i]?。

如果不存在?nums[j]?,那么第二大整数为?-1?。

  • 比方说,数组?[1, 2, 4, 3]?中,1?的第二大整数是?4?,2?的第二大整数是?3?,3?和?4?的第二大整数是?-1?。

请你返回一个整数数组?answer?,其中?answer[i]?nums[i]?的第二大整数。

示例 1:

输入:nums = [2,4,0,9,6]
输出:[9,6,6,-1,-1]
解释:
下标为 0 处:2 的右边,4 是大于 2 的第一个整数,9 是第二个大于 2 的整数。
下标为 1 处:4 的右边,9 是大于 4 的第一个整数,6 是第二个大于 4 的整数。
下标为 2 处:0 的右边,9 是大于 0 的第一个整数,6 是第二个大于 0 的整数。
下标为 3 处:右边不存在大于 9 的整数,所以第二大整数为 -1 。
下标为 4 处:右边不存在大于 6 的整数,所以第二大整数为 -1 。
所以我们返回 [9,6,6,-1,-1] 。

示例 2:

输入:nums = [3,3]
输出:[-1,-1]
解释:
由于每个数右边都没有更大的数,所以我们返回 [-1,-1] 。

提示:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109

实现代码与解析:

单调栈 & 优先级队列

class Solution {
    public int[] secondGreaterElement(int[] nums) {
        
        Stack<Integer> stk = new Stack<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int[] res = new int[nums.length];
        Arrays.fill(res, -1);

        for (int i = 0; i < nums.length; i++) {

            while (!pq.isEmpty() && pq.peek()[0] < nums[i]) {
                int t = pq.peek()[1];
                pq.poll();
                res[t] = nums[i];
            }

            while (!stk.isEmpty() && nums[stk.peek()] < nums[i]) {
                int t = stk.peek();
                stk.pop();
                pq.offer(new int[]{nums[t], t});
            }
            stk.push(i);
        }
        return res;
    }           
}

原理思路:

? ? ? ? 遍历数组,单调栈,求出第一个大于对应位置的数,若有,放入优先级队列中。

所以,在单调栈中的数,代表寻找第一个大于其的数是否存在。

? ? ? ??优先级队列里的数,代表寻找第二个大于其的数,只有在单调栈中判断后弹出

的数才会放入优先级队列中。结果数组也是在优先级队列中求出。

? ? ? ? 优先级队列是为了排序,方便数之间的对比,弹出,然后求出对应位置的结果。

文章来源:https://blog.csdn.net/Cosmoshhhyyy/article/details/134981983
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。