1.题目描述

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] 是如上所述的 下一个更大元素 。

2.示例

示例 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 。

3.代码实现及思路

package com.yt.leetcode;/*** @auther yt* @address https://www.cnblogs.com/y-tao/*/
public class LeetCode496 {public static void main(String[] args) {int[] nums1 = {1};int[] nums2 = {1};Solution496 solution496 = new Solution496();int[] nextGreaterElement = solution496.nextGreaterElement(nums1, nums2);for (int i = 0; i < nextGreaterElement.length; i++) {System.out.println(nextGreaterElement[i]);}}
}//复杂度有点高，后期优化
class Solution496 {public int[] nextGreaterElement(int[] nums1, int[] nums2){int[] ans = new int[nums1.length];//遍历nums1for (int i = 0; i < nums1.length; i++) {//遍历nums2for (int j = 0; j < nums2.length; j++) {//因为题目说，nums1是nums2的子集，那么nums1中的元素一定可以在nums2中找到if (nums1[i] == nums2[j]){//遍历相当元素后面的所有元素while (j < nums2.length) {
//                    闯关式思想：if (j + 1 == nums2.length)没找到元素就不用往下走了if (j + 1 == nums2.length){ans[i] = -1;break;}//元素之间的判断，判断nums2后面的元素是否存在第一个比num1大的数if (nums2[j + 1] > nums1[i]) {//找到第一个大的元素就退出内循环ans[i] = nums2[j + 1];break;} else if (nums2[j + 1] < nums1[i]) {//后一个元素不大于，就后一位j++;} else {//遍历完毕num2都没有找到，就赋值为-1，并退出循环ans[i] = -1;break;}}}}}return ans;}
}

4.来源

力扣(LeetCode)
链接：力扣

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！