leetcode496：下一个更大元素 I（next-greater-element-i）

[carloscn]

问题描述

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] <= 104
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中

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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/next-greater-element-i

[carloscn]

问题分析：

static int32_t next_greater_element(int32_t *array_1,
                                    size_t *array_1_sz,
                                    const int32_t *array_2,
                                    size_t array_2_sz)
{
    int32_t ret = 0;
    size_t i = 0, j = 0;
    int32_t max = 0;
    int32_t target_val = 0;
    size_t count = 0;

    UTILS_CHECK_PTR(array_1);
    UTILS_CHECK_PTR(array_2);
    UTILS_CHECK_LEN(*array_1_sz);
    UTILS_CHECK_LEN(array_2_sz);

    for (i = 0; i < *array_1_sz; i ++) {
        target_val = array_1[i];
        for (j = 0; j < array_2_sz; j ++) {
            if (target_val == array_2[j]) {
                if ((j < array_2_sz - 1) && (array_2[j + 1] > target_val)) {
                    array_1[count] = array_2[j + 1];
                } else {
                    array_1[count] = -1;
                }
                count ++;
            }
        }
    }

    *array_1_sz = count;

finish:
    return ret;
}

[carloscn]

code

https://github.com/carloscn/structstudy/blob/master/c_programming/array/37_next-greater-element-i_496.c

result