【LeetCode】每日一题 2023_12_12 下一个更大元素 IV(堆,优先级队列/单调栈)
2023-12-13 07:00:17
刷题前唠嗑
LeetCode?启动!!!
时隔两天,LeetCode 每日一题重新开张,流感已经不能阻挡我的脚步了!
题目:下一个更大元素 IV
题目链接:2454. 下一个更大元素 IV
题目描述
代码与解题思路
题目非常的好理解啊,这个读题难度让人感受不到他是一个 hard,而且这道题目一眼顶真,暴力解法非常的简单,直接一个一个数枚举就行了,但是一个一个数枚举肯定是会超时的,题目给的数据是 10 的 5 次,也就是说怎么说都得 N*logN 的复杂度,N 方肯定是超时的
这种根据大小找数字的题目,不难想到可以用优先级队列来维护,用题目给的样例分析一下,我们可以设计这样一个思路
- 遍历 nums 数组,每次遍历都入栈
- 如果出现当前遍历的数比栈顶大的情况,就让栈顶入优先级队列,直到所有比当前数小的栈顶都进优先级队列,因为当前的数就是刚刚入队的数的第一个大的数(题目要求的是第二个大的数)
- 当新的遍历的大于优先级队列中的数时,这个数就是所谓的第二个大的数,知道把所有符合情况的数都出队,修改 ans 数组
这样我们就是利用了优先级队列的特性,维护了一个小堆
func secondGreaterElement(nums []int) []int {
ans := make([]int, len(nums))
for i, _ := range nums { // 初始化成 -1
ans[i] = -1
}
st1, st2 := []int{}, []int{}
for i, v := range nums {
for len(st2) > 0 && nums[st2[len(st2)-1]] < v { // 这次遍历的值比 st2 栈顶大
ans[st2[len(st2)-1]] = v
st2 = st2[:len(st2)-1]
}
j := len(st1)-1
for j >= 0 && nums[st1[j]] < v { // 找到 v 的第一大整数
j--
}
st2 = append(st2, st1[j+1:]...) // 将 v 的第一大整数及其之前的区间直接从栈 1 移入栈 2
st1 = append(st1[:j+1], i) // 每次将当前位置的下标入栈 1
}
return ans
}
我们发现,这里的栈其实是一个单调的递减栈,我们可以利用他的特性,通过整体追加的形式模拟优先级队列,这样我们就能通过用两个单调栈 O(N) 一次遍历就能得出答案
代码的核心思路其实就是对题目要求的寻找第二个大的数的模拟。
文章来源:https://blog.csdn.net/Locky136/article/details/134941131
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!