【LeetCode】每日一题 2023_12_12 下一个更大元素 IV(堆,优先级队列/单调栈)

2023-12-13 07:00:17

刷题前唠嗑


LeetCode?启动!!!

时隔两天,LeetCode 每日一题重新开张,流感已经不能阻挡我的脚步了!

题目:下一个更大元素 IV

题目链接:2454. 下一个更大元素 IV

题目描述

代码与解题思路

题目非常的好理解啊,这个读题难度让人感受不到他是一个 hard,而且这道题目一眼顶真,暴力解法非常的简单,直接一个一个数枚举就行了,但是一个一个数枚举肯定是会超时的,题目给的数据是 10 的 5 次,也就是说怎么说都得 N*logN 的复杂度,N 方肯定是超时的

这种根据大小找数字的题目,不难想到可以用优先级队列来维护,用题目给的样例分析一下,我们可以设计这样一个思路

  1. 遍历 nums 数组,每次遍历都入栈
  2. 如果出现当前遍历的数比栈顶大的情况,就让栈顶入优先级队列,直到所有比当前数小的栈顶都进优先级队列,因为当前的数就是刚刚入队的数的第一个大的数(题目要求的是第二个大的数)
  3. 当新的遍历的大于优先级队列中的数时,这个数就是所谓的第二个大的数,知道把所有符合情况的数都出队,修改 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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。