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

文章目录

• 刷题前唠嗑
• 题目：下一个更大元素 IV

刷题前唠嗑

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) 一次遍历就能得出答案

代码的核心思路其实就是对题目要求的寻找第二个大的数的模拟。