leetcode496. 下一个更大元素 I

leetcode 496. 下一个更大元素 I

题目描述

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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

查找右侧最大值\

1. 寻找n1中每个值在n2中的位置,
2. 找寻右部是否有大于的元素,有返回数字,没有返回-1

• 时间复杂度(O(n^2))
• 空间复杂度(O(1))

执行结果

法1

func nextGreaterElement(nums1 []int, nums2 []int) []int {
 r := make([]int, len(nums1))//建立一个数组储存结果
 for j := 0; j < len(nums1); j++ {
  r[j] = -1//没有就是-1
  for i, b := 0, false; i < len(nums2); i++ {
   if nums2[i] == nums1[j] {//找到在n2表中的位置,减判断条件赋值为真
    b = true
   }
   if b && nums2[i] > nums1[j] {//找寻后面是否存在一个比n1中的值大的数,没有就是-1
    r[j] = nums2[i]
    break
   }
  }
 }
 return r
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 4 ms , 在所有 Go 提交中击败了 72.63% 的用户 内存消耗： 2.7 MB , 在所有 Go 提交中击败了 95.96% 的用户 通过测试用例： 16 / 16 炫耀一下:

法2

优化方案
将判断bool作为基础,可以减少判断的次数优化性能

func nextGreaterElement(nums1 []int, nums2 []int) []int {
 r := make([]int, len(nums1)) //建立一个数组储存结果
 for j := 0; j < len(nums1); j++ {
  r[j] = -1 //没有就是-1
  for i, b := 0, false; i < len(nums2); i++ {
   if !b {
    if nums2[i] == nums1[j] { //找到在n2表中的位置,减判断条件赋值为真
     b = true
    }
   } else if nums2[i] > nums1[j] { //找寻后面是否存在一个比n1中的值大的数,没有就是-1
    r[j] = nums2[i]
    break
   }
  }
 }
 return r
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 4 ms , 在所有 Go 提交中击败了 72.63% 的用户 内存消耗： 2.7 MB , 在所有 Go 提交中击败了 95.96% 的用户 通过测试用例： 16 / 16