What is the time complexity of the Next Greater Element I problem?

The time complexity is O(n + m), where n is the length of nums2 and m is the length of nums1, due to the stack processing and hash table lookups.

How can the stack be used in the Next Greater Element I problem?

The stack is used to store elements of nums2 while traversing it from right to left, ensuring that we can find the next greater element for each item in constant time.

What is the role of the hash table in solving Next Greater Element I?

The hash table stores the next greater element for each element in nums2, allowing for constant time lookup when processing nums1.

How does the space complexity of this solution compare to other approaches?

The space complexity is O(n), where n is the length of nums2, due to the stack and hash table. This is efficient compared to a brute-force approach, which would require O(m * n) space.

Can this solution be adapted for similar problems?

Yes, this approach can be adapted to solve similar problems, such as finding the previous greater element or handling different types of range queries.

#496

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

下一个更大元素 I

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置右侧的第一个比 x 大的元素。给你两个没有重复元素的数组 nums1 和 nums2 ，下标从 0 开始计数，其中 nums1 是 nums2 的子集。对于每个 0 ，找出满足 nums1[i] == n…

数组哈希表栈单调栈

题目描述

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置右侧的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

示例 1：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

示例 2：

输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

提示：

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 10⁴
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中

进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

lightbulb

解题思路

方法一：单调栈

我们可以从右往左遍历数组 $\textit{nums2}$ ，维护一个从栈顶到栈底单调递增的栈 $\textit{stk}$ ，并且用哈希表 $\textit{d}$ 记录每个元素的下一个更大元素。

遍历到元素 $x$ 时，如果栈不为空且栈顶元素小于 $x$ ，我们就不断弹出栈顶元素，直到栈为空或者栈顶元素大于等于 $x$ 。此时，如果栈不为空，栈顶元素就是 $x$ 的下一个更大元素，否则 $x$ 没有下一个更大元素。

最后我们遍历数组 $\textit{nums1}$ ，根据哈希表 $\textit{d}$ 得到答案。

时间复杂度 $O(m + n)$ ，空间复杂度 $O(n)$ 。其中 $m$ 和 $n$ 分别为数组 $\textit{nums1}$ 和 $\textit{nums2}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stk = []
        d = {}
        for x in nums2[::-1]:
            while stk and stk[-1] < x:
                stk.pop()
            if stk:
                d[x] = stk[-1]
            stk.append(x)
        return [d.get(x, -1) for x in nums1]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidates should be able to explain how the stack is used to maintain the next greater elements in a monotonic manner.
question_mark
Look for a clear understanding of how hash tables optimize the lookup process after processing nums2.
question_mark
Candidates should discuss the time and space complexities and how they are optimized compared to a brute-force solution.

warning

常见陷阱

外企场景

error
Not using the stack to maintain the next greater elements in a monotonic order, which leads to a less efficient solution.
error
Overlooking the need to map elements of nums2 to their next greater element using a hash table, leading to slower lookups.
error
Misunderstanding the problem constraints, leading to inefficient or incorrect handling of array indices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling multiple queries for different nums1 arrays with the same nums2 array.
arrow_right_alt
Optimizing further using additional data structures, like trees or heaps, to support different types of range queries.
arrow_right_alt
Adapting the approach for finding the previous greater element instead of the next greater element.

help

常见问题

外企场景

继续练习

#1124 表现良好的最长时间段 #456 132 模式 #581 最短无序连续子数组