下一个更大元素 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 <= 10000 <= nums1[i], nums2[i] <= 10^4nums1和nums2中所有整数 互不相同nums1中的所有整数同样出现在nums2中
进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？
倒序是入栈前计算当前元素（因为每次处理的都是当前元素，所以不需要存索引）的下一个更大元素。 正序是入栈后计算栈内元素（历史数据，必须存索引以便定位）的下一个更大元素。 无论正序还是倒序，计算前都要先处理栈，使之递减。
递减栈，倒序遍历
注意 nums1 是 nums2 的子集，所以我们可以根据nums2得到一个哈希表：元素 x -> x 的下一个最大元素。 得到这个哈希表的过程要用到递减栈和倒序遍历。栈里存元素值。入栈的时候确定栈外元素的结果，确定完再入栈。
注意我们要计算的是下一个更大元素不是下一个更大元素的距离，因此栈里存的是元素。
倒序遍历从数组的末尾开始，将元素依次入栈，并在入栈之前清除掉栈中所有小于或等于当前元素的值。这样，栈顶元素始终是当前元素右侧的第一个更大元素。
由于我们从右向左遍历，所以在处理当前元素时，栈中已经维护好了该元素右侧的更大元素。
我们要求的是每个元素的下一个更大元素，所以在处理当前元素时，我们需要后面的数据，所以此时栈里要存后面的数据，所以要倒序遍历。
class Solution {
int[] nextGreaterElement(int[] nums1, int[] nums2) {
// 记录 nums2 中每个元素的下一个更大元素
int[] greater = nextGreaterElement(nums2);
// 把greater数组转化成映射：元素 x -> x 的下一个最大元素
Map<Integer, Integer> greaterMap = new HashMap<>();
for (int i = 0; i < nums2.length; i++) {
greaterMap.put(nums2[i], greater[i]);
}
// nums1 是 nums2 的子集，所以根据 greaterMap 可以得到结果
int[] res = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
res[i] = greaterMap.get(nums1[i]);
}
return res;
}
int[] nextGreaterElement(int[] nums) {
int n = nums.length;
// 存放答案的数组
int[] res = new int[n];
Deque<Integer> s = new ArrayDeque<>();
// 倒着往栈里放。栈里存元素值。
for (int i = n - 1; i >= 0; i--) {
// 如果栈顶元素小于等于当前元素，那么栈顶元素就不可能是当前元素的下一个更大元素，
while (!s.isEmpty() && s.peek() <= nums[i]) {
s.pop();
}
// 栈顶元素就是 nums[i] 身后的更大元素。倒序遍历是先计算，再入栈，计算前要处理一下栈，使之递减。
res[i] = s.isEmpty() ? -1 : s.peek();
s.push(nums[i]);
}
return res;
}
}时间复杂度O(m+n)，空间复杂度O(n)。
递减栈，正序遍历
先入栈，弹栈的时候确定栈内元素的结果。和倒序遍历的区别是关注点不一样，倒序遍历关注的是栈外的元素，正序遍历关注的是栈内的元素。
当前元素是栈顶元素的下一个更大元素，倒序遍历时，栈顶元素是当前元素的下一个更大元素。
class Solution {
int[] nextGreaterElement(int[] nums1, int[] nums2) {
// 记录 nums2 中每个元素的下一个更大元素
int[] greater = nextGreaterElement(nums2);
// 转化成映射：元素 x -> x 的下一个最大元素
Map<Integer, Integer> greaterMap = new HashMap<>();
for (int i = 0; i < nums2.length; i++) {
greaterMap.put(nums2[i], greater[i]);
}
// nums1 是 nums2 的子集，所以根据 greaterMap 可以得到结果
int[] res = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
res[i] = greaterMap.get(nums1[i]);
}
return res;
}
int[] nextGreaterElement(int[] nums) {
int n = nums.length;
// 存放答案的数组
int[] res = new int[n];
// 题目要求找不到更大元素时返回-1
Arrays.fill(res, -1);
Deque<Integer> s = new ArrayDeque<>();
// 正着往栈里放，栈里存待计算位置的索引，不能存元素值！
for (int i = 0; i < n; i++) {
// 每遇到一个新元素，就检查一下是否大于等于栈顶元素，如果大于等于，则顺便计算一下栈顶元素的下一个更大元素。
while (!s.isEmpty() && nums[s.peek()] <= nums[i]) {
int pre = s.pop();
// 重点。我们计算的是栈内元素的下一个更大元素。倒序时是入栈前计算。正序时是入栈后计算栈内元素的下一个更大元素。无论正序还是倒序，
// 计算前都要先处理栈，使之递减。
res[pre] = nums[i];
}
// 清完栈后再push
s.push(i);
}
return res;
}
}时间复杂度O(m+n)，空间复杂度O(n)。