当前位置: 面试刷题>> 下一个更大的元素 (经典算法题500道)


题目描述补充

题目:下一个更大的元素 I

给定两个没有重复元素的数组 nums1nums2,其中 nums1nums2 的子集(即 nums1 中的每个元素都一定可以在 nums2 中找到)。现在,对于 nums1 中的每个元素,找出在 nums2 中它的下一个比它大的元素。nums1nums2 中的元素均为唯一的。

示例 1:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
    对于 nums1 中的数字 4,你无法在 nums2 中找到下一个更大的数字,因此输出 -1。
    对于 nums1 中的数字 1,下一个更大的数字是 3。
    对于 nums1 中的数字 2,你无法在 nums2 中找到下一个更大的数字,因此输出 -1。

示例 2:

输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
    对于 nums1 中的数字 2,下一个更大的数字是 3。
    对于 nums1 中的数字 4,你无法在 nums2 中找到下一个更大的数字,因此输出 -1。

PHP 示例代码

function nextGreaterElement($nums1, $nums2) {
    $stack = []; // 用于存储nums2的索引
    $nextGreater = array_fill(0, count($nums2), -1); // 初始化nextGreater数组,默认值为-1
    $numMap = array_flip($nums2); // 创建nums2的键值对映射,用于快速查找

    foreach ($nums2 as $i => $num) {
        while (!empty($stack) && $num > $nums2[end($stack)]) {
            $nextGreater[array_pop($stack)] = $num;
        }
        $stack[] = $i;
    }

    $result = [];
    foreach ($nums1 as $num) {
        $result[] = $nextGreater[$numMap[$num]];
    }

    return $result;
}

// 测试
$nums1 = [4, 1, 2];
$nums2 = [1, 3, 4, 2];
print_r(nextGreaterElement($nums1, $nums2));

Python 示例代码

def nextGreaterElement(nums1, nums2):
    stack = []
    nextGreater = {num: -1 for num in nums2}

    for num in nums2:
        while stack and num > nums2[stack[-1]]:
            nextGreater[nums2[stack.pop()]] = num
        stack.append(len(nums2) - 1 - nums2[::-1].index(num))

    return [nextGreater[num] for num in nums1]

# 测试
nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
print(nextGreaterElement(nums1, nums2))

JavaScript 示例代码

function nextGreaterElement(nums1, nums2) {
    const stack = [];
    const nextGreater = {};
    for (const num of nums2) {
        nextGreater[num] = -1;
    }

    for (let i = 0; i < nums2.length; i++) {
        while (stack.length > 0 && nums2[i] > nums2[stack[stack.length - 1]]) {
            nextGreater[nums2[stack.pop()]] = nums2[i];
        }
        stack.push(i);
    }

    return nums1.map(num => nextGreater[num]);
}

// 测试
const nums1 = [4, 1, 2];
const nums2 = [1, 3, 4, 2];
console.log(nextGreaterElement(nums1, nums2));

码小课网站中有更多相关内容分享给大家学习,包括算法基础、数据结构、面试技巧等,帮助大家提升编程能力和面试成功率。

推荐面试题