Leetcode 496 下一个更大元素 I

题目描述

nums1 中数字 x下一个更大元素 是指 xnums2 中对应位置 右侧第一个x 大的元素。

给你两个 没有重复元素 的数组 nums1nums2 ,下标从 0 开始计数,其中nums1nums2 的子集。

对于每个 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;
    }
}
上一篇:adb获取Android系统属性(adb shell getprop ***)数据来源


下一篇:Cypress-项目目录介绍、一个简单的demo