河源网站搭建费用,500m网站,分类信息网站如何优化,title 网站建设【力扣】496. 下一个更大元素 I nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。给你两个没有重复元素的数组 nums1 和 nums2 #xff0c;下标从 0 开始计数#xff0c;其中nums1 是 nums2 的子集。 对于每个 0 i 下标从 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] 1 0 4 10^4 104 nums1和nums2中所有整数 互不相同 nums1 中的所有整数同样出现在 nums2 中
题解
单调栈哈希
import java.util.*;public class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {//单调栈StackInteger stack new Stack();//存放结果最终结果大小和nums1一样int[] result new int[nums1.length];Arrays.fill(result, -1);//求nums1和nums2的映射关系HashMapInteger, 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;}
}
