0496. Next Greater Element I
===========================
题目信息
--------
:题号: 0496
:难度: Easy
:主题: 两个无重复数组、子集关系、右侧首个更大值、结果对齐
:原题: `LeetCode 0496 `_
:重点: ``nums1`` 是 ``nums2`` 的子集、先在 ``nums2`` 定位同值元素、只搜索其右侧、返回第一个严格更大的值
题目重述
--------
给定两个不含重复元素的整数数组 ``nums1`` 和 ``nums2``,并保证 ``nums1`` 中的每个值都出现在 ``nums2`` 中。对 ``nums1`` 中的每个元素 ``x``,先找到它在 ``nums2`` 中的位置,再在该位置右侧寻找第一个严格大于 ``x`` 的元素。
按 ``nums1`` 的原顺序返回查询结果;若某个元素右侧不存在更大值,则对应位置返回 ``-1``。两个数组长度位于 ``[1, 1000]``,元素位于 ``[0, 10^4]``。
自建示例
--------
两个查询都存在右侧更大值:
.. code-block:: text
输入:nums1 = [2,4],nums2 = [1,2,3,4,5]
输出:[3,5]
解释:2 右侧第一个更大值是 3;4 右侧第一个更大值是 5。
右侧元素全部更小:
.. code-block:: text
输入:nums1 = [5],nums2 = [5,4,3]
输出:[-1]
解释:5 在 nums2 的右侧没有严格更大的元素。
单调栈预处理 nums2 的下一个更大值
---------------------------------
从 ``nums2`` 右向左扫描,栈中保持一组可能成为后续元素“右侧第一个更大值”的候选。处理当前值时,栈顶小于等于当前值的候选不可能再成为当前值或更左元素的答案,全部弹出;剩下的栈顶就是当前值右侧第一个严格更大的元素。
把每个 ``nums2`` 值的答案存入哈希表,最后按 ``nums1`` 原顺序查询即可。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
std::vector nextGreaterElement(
std::vector& nums1, std::vector& nums2) {
std::unordered_map nextGreater;
std::vector stack;
for (int i = static_cast(nums2.size()) - 1; i >= 0; --i) {
while (!stack.empty() && stack.back() <= nums2[i]) {
stack.pop_back();
}
nextGreater[nums2[i]] = stack.empty() ? -1 : stack.back();
stack.push_back(nums2[i]);
}
std::vector result;
result.reserve(nums1.size());
for (int value : nums1) result.push_back(nextGreater[value]);
return result;
}
};
代码分析
--------
每个元素入栈一次、出栈至多一次,栈顶在弹出后不会重新成为候选;因此预处理 ``nums2`` 的时间复杂度为 ``O(|nums2|)``,查询 ``nums1`` 为 ``O(|nums1|)``,额外空间复杂度为 ``O(|nums2|)``。