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 。
题目来源：力扣（LeetCode）
哈希表+单调栈解决思路
能否写出：能写出来
时间：20分钟
思路：
第一次写，没有看懂题目，以为是下一个更大元素是指nums[i]与nums[i+1]的大小关系，并没有考虑到与其后的更多元素的比较。
(╯°Д°)╯︵ ┻━┻
测试用例:[1,3,5,2,4]
[6,5,4,3,2,1,7]
测试结果:[7,-1,-1,-1,-1]
期望结果:[7,7,7,7,7]
class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums2.length; i++) { //这里出错，只比较了nums[i]与nums[i+1] if (i == nums2.length-1 || nums2[i] > nums2[i + 1]) { map.put(nums2[i], -1); } else { map.put(nums2[i], nums2[i + 1]); } } int[] result = new int[nums1.length]; for (int i = 0; i < nums1.length; i++) { result[i] = map.get(nums1[i]); } return result; } }
第二版
思路：
- 创建一个哈希表map，用于存储nums2中每个元素的下一个更大元素。键为元素值，值为下一个更大元素。
- 创建一个空的单调栈stack，用于存储尚未找到下一个更大元素的元素索引。
- 遍历nums2中的每个元素：
- 当stack非空且当前元素num2大于栈顶元素时，将栈顶元素出栈，并将该元素和num2[i]建立映射关系，即
map.put(stack.pop(), nums2[i]) - 将当前元素num2的索引入栈，表示该元素尚未找到下一个更大元素。
- 遍历nums1中的每个元素：
- 在map中查找num1的下一个更大元素，若存在则将其作为结果，否则为-1。
// 仅是我的思路代码，leetcode上大神更厉害 class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { HashMap<Integer, Integer> map = new HashMap<>(); Stack<Integer> stack = new Stack(); for (int i = 0; i < nums2.length; i++) { while (!stack.isEmpty()&& nums2[i] > stack.peek()){ map.put(stack.pop(),nums2[i]); } stack.push(nums2[i]); } int[] result = new int[nums1.length]; for (int i = 0; i < nums1.length; i++) { //如果map中不存在，则返回输入的k,v; result[i] = map.getOrDefault(nums1[i],-1); } return result; } }
时间复杂度：O(m+n)
遍历nums2时，需要将元素入栈并进行比较，而nums2的长度为n。同时，遍历nums1时，需要在哈希表中查找元素的下一个更大元素，而nums1的长度为m。因此，算法的时间复杂度可以表示为O(m + n)
空间复杂度：O(n)
存储哈希表时候所需的空间。
暴力解决
没什么是循环解决不了的，有就加多一个循环的。(╯°Д°)╯︵ ┻━┻
思路：
对于nums1中的每个元素，在nums2中找到该元素的位置，然后从该位置开始遍历nums2，找到第一个大于该元素的值，作为结果。如果找不到大于该元素的值，则返回-1。
class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { int[] result = new int[nums1.length]; //循环num1数组 for (int i = 0; i < nums1.length; i++) { int num1 = nums1[i]; int index = -1; //循环num2数组，查询num1[i]在num2的位置 for (int j = 0; j < nums2.length; j++) { if (nums2[j] == num1) { index = j; break; } } //默认最大 result[i] = -1; //继续在num2中找num1[i]往后最大的数 for (int j = index + 1; j < nums2.length; j++) { if (nums2[j] > num1) { //找到输出到result数组 result[i] = nums2[j]; break; } } } return result; } }
时间复杂度：O(mn) num1*num2
空间复杂度：O(1)
