题目描述

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 。

方法一：暴力

我们可以暴力地逐个计算 \(\textit{nums}_1\)中的每个元素值 \(\textit{nums}_1[i]\) 在 \(\textit{nums}_2\)中对应位置的右边的第一个比 \(\textit{nums}_1[i]\) 大的元素值。具体地，我们使用如下方法：

• 初始化与 \(\textit{nums}_1\) 等长的查询数组 \(\textit{res}\)。

• 遍历 \(\textit{nums}_1\)中的所有元素，不妨设当前遍历到元素为 \(\textit{nums}_1[i]\):

  • 从前向后遍历 \(\textit{nums}_2\)中的元素，直至找到 \(\textit{nums}_2[j] = \textit{nums}_1[i]\)
  • 从 \(j+1\) 开始继续向后遍历，直至找到 \(\textit{nums}_2[k] > \textit{nums}_2[j]\)
  • 如果找到了 \(\textit{nums}_2[k]\)，则将 \(\textit{res}[i]\) 置为 \(\textit{nums}_2[k]n\)]，否则将 \(\textit{res}[i]\) 置为 \(−1\)。

  数组 \(\textit{res}\)即为最终结果。

  class Solution {
      public int[] nextGreaterElement(int[] nums1, int[] nums2) {
          int length = nums2.length;
          int[] ans = new int[nums1.length];
          for (int i = 0; i < nums1.length; i++) {
              int currNums1 = nums1[i];
              int j = 0;
              while (nums2[j]!=currNums1) {
                  j++;
              }
              int index = j + 1;
              while (index < length && nums2[index] <= currNums1) {
                  ++index;
              }
              if (index < length) {
                  ans[i] = nums2[index];
              } else {
                  ans[i] = -1;
              }
          }
          return ans;
      }
  }
  

方法二：单调栈

一旦要求下一个更大的元素，就是用单调栈解

我们可以先预处理 \(\textit{nums}_2\)，使查询 \(\textit{nums}_1\)中的每个元素在 \(\textit{nums}_2n\) 中对应位置的右边的第一个更大的元素值时不需要再遍历 \(\textit{nums}_2\)。于是，我们将题目分解为两个子问题：

• 第 \(1\) 个子问题：如何更高效地计算 \(\textit{nums}_2\) 中每个元素右边的第一个更大的值；
• 第 \(2\) 个子问题：如何存储第 \(1\) 个子问题的结果。

我们可以使用单调栈来解决第 \(1\) 个子问题。倒序遍历 \(\textit{nums}_2\)，并用单调栈中维护当前位置右边的更大的元素列表，从栈底到栈顶的元素是单调递减的。

具体地，每次我们移动到数组中一个新的位置 \(i\)，就将当前单调栈中所有小于 \(\textit{nums}_2[i]\) 的元素弹出单调栈，当前位置右边的第一个更大的元素即为栈顶元素，如果栈为空则说明当前位置右边没有更大的元素。随后我们将位置 \(i\) 的元素入栈。

因为题目规定了 \(\textit{nums}_2n\)是没有重复元素的，所以我们可以使用哈希表来解决第 \(2\) 个子问题，将元素值与其右边第一个更大的元素值的对应关系存入哈希表。

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int length = nums2.length;
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            int currNums1 = nums1[i];
            int j = 0;
            while (nums2[j]!=currNums1) {
                j++;
            }
            int index = j + 1;
            while (index < length && nums2[index] <= currNums1) {
                ++index;
            }
            if (index < length) {
                ans[i] = nums2[index];
            } else {
                ans[i] = -1;
            }
        }
        return ans;
    }
}