LeetCode 496. 下一个更大元素 I

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 496. 下一个更大元素 I

思路分析

单调栈 + 哈希表

我们可以使用栈和哈希表来解决这个问题。具体思路如下：

初始化一个栈和一个哈希表 nextGreater，用于存储每个元素的下一个更大元素。

遍历 nums2，对于每个元素：

如果栈不为空且当前元素大于栈顶元素，则更新 nextGreater 中栈顶元素对应的值为当前元素，并弹出栈顶元素。

将当前元素压入栈。

遍历 nums1，根据 nextGreater 哈希表中的值构建结果数组 res。

最终返回 res 数组。

参考代码

func nextGreaterElement(nums1 []int, nums2 []int) []int {
	res := make([]int, len(nums1))
	nextGreater := make(map[int]int)
	var stack []int

	for _, num := range nums2 {
		for len(stack) > 0 && num > stack[len(stack)-1] {
			nextGreater[stack[len(stack)-1]] = num
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, num)
	}

	for i, num := range nums1 {
		if val, ok := nextGreater[num]; ok {
			res[i] = val
		} else {
			res[i] = -1
		}
	}

	return res
}

write your code here

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/49007619