【力扣】496. 下一个更大元素 I ＜单调栈、模拟＞

【力扣】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] <= $10^4$
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中

题解

单调栈+哈希

import java.util.*;public class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {//单调栈Stack<Integer> stack = new Stack<>();//存放结果最终结果，大小和nums1一样int[] result = new int[nums1.length];Arrays.fill(result, -1);//求nums1和nums2的映射关系HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums1.length; i++) {// key为数值，value为下标map.put(nums1[i], i);}//先放第一个元素的下标进单调栈stack.add(0);//单调栈遍历数组nums2for (int i = 1; i < nums2.length; i++) {//当前遍历的元素和栈口元素的比较if (nums2[i] <= nums2[stack.peek()]) {stack.push(i);}else {//循环比较while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {if (map.containsKey(nums2[stack.peek()])) {Integer index = map.get(nums2[stack.peek()]);result[index] = nums2[i];}stack.pop();}stack.push(i);}}return result;}
}

暴力：

public class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int[] result = new int[nums1.length];//遍历nums1的元素，逐个去nums2找for (int i = 0; i < nums1.length; ++i) {//先找到相等的位置int j = 0;while (j < nums2.length && nums2[j] != nums1[i]) {j++;}//继续找右边第一个比它大的int k = j + 1;while (k < nums2.length && nums2[k] < nums2[j]) {k++;}//k < nums2.length说明找到了右边比它大的result[i] = (k < nums2.length) ? nums2[k] : -1;}return result;}
}