中企动力网站优化,uml电子商务网站建设文档,智慧团建如何转团关系,我的网站怎么做3妹#xff1a;“太阳当空照#xff0c;花儿对我笑#xff0c;小鸟说早早早#xff0c;你为什么背上炸药包” 2哥 :3妹#xff0c;什么事呀这么开发。 3妹#xff1a;2哥你看今天的天气多好啊#xff0c;阳光明媚、万里无云、秋高气爽#xff0c;适合秋游。 2哥#x…
3妹“太阳当空照花儿对我笑小鸟说早早早你为什么背上炸药包” 2哥 :3妹什么事呀这么开发。 3妹2哥你看今天的天气多好啊阳光明媚、万里无云、秋高气爽适合秋游。 2哥是啊立冬之后天气多以多云为主好不容易艳阳高照。可是你不能秋游赶紧收拾收拾上班去啦 3妹哼 好吧~ 2哥给你出了一道题发你微信里了 上班通勤的路上记得看一下回来问你答案~ 3妹知道啦难不倒我
题目
给你一个下标从 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 10^5 0 nums[i] 10^9
思路 单调栈 优先队列, 我们可以考虑将原始问题简化为计算数组中每个数字的下一个比它大的数字。为了解决这一问题我们可以利用「单调栈」算法。该算法的核心思想是利用一个栈来存储数组元素的下标。在遍历数组时对于每个元素执行以下操作如果当前元素大于栈顶元素对应的值说明找到了栈顶元素的下一个更大的数字将栈顶元素出栈并更新结果数组。如果当前元素小于等于栈顶元素对应的值将当前元素的下标压入栈中保持栈的单调递减性质。这样最终结果数组中存储的就是每个数字的下一个比它大的数字如果存在的话如果没有更大的数字则对应位置的值为 −1。
java代码
class Solution {public int[] secondGreaterElement(int[] nums) {int length nums.length;int[] secondGreater new int[length];Arrays.fill(secondGreater, -1);DequeInteger stack new ArrayDequeInteger();PriorityQueueint[] pq new PriorityQueueint[]((a, b) - a[1] - b[1]);for (int i 0; i length; i) {int num nums[i];while (!pq.isEmpty() pq.peek()[1] num) {int index pq.poll()[0];secondGreater[index] num;}while (!stack.isEmpty() nums[stack.peek()] num) {int index stack.pop();pq.offer(new int[]{index, nums[index]});}stack.push(i);}return secondGreater;}
}
