网站搜索引擎优化方案,ui设计是什么意思啊,创艺装饰公司,wordpress顶部广告怎么添加目录 2454. 下一个更大元素 IV
题目描述#xff1a;
实现代码与解析#xff1a;
单调栈 优先级队列
原理思路#xff1a; 2454. 下一个更大元素 IV
题目描述#xff1a; 给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数#xff0c;你必须找…目录 2454. 下一个更大元素 IV
题目描述
实现代码与解析
单调栈 优先级队列
原理思路 2454. 下一个更大元素 IV
题目描述 给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数你必须找到对应元素的 第二大 整数。
如果 nums[j] 满足以下条件那么我们称它为 nums[i] 的 第二大 整数
j inums[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 1050 nums[i] 109
实现代码与解析
单调栈 优先级队列
class Solution {public int[] secondGreaterElement(int[] nums) {StackInteger stk new Stack();PriorityQueueint[] 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;}
}
原理思路 遍历数组单调栈求出第一个大于对应位置的数若有放入优先级队列中。
所以在单调栈中的数代表寻找第一个大于其的数是否存在。 优先级队列里的数代表寻找第二个大于其的数只有在单调栈中判断后弹出
的数才会放入优先级队列中。结果数组也是在优先级队列中求出。 优先级队列是为了排序方便数之间的对比弹出然后求出对应位置的结果。
