单调栈-leetcode-每日练习
2022.5.14
通过这个题，了解掌握单调栈
[496. 下一个更大元素 I](https://lee tcode.cn/problems/next-greater-element-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] <= 104nums1和nums2中所有整数 互不相同nums1中的所有整数同样出现在nums2中
**进阶：**你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？
思路：
法一：
双指针法：循环遍历
指针i指向当前nums1里面的目标值，指针j先遍历找到目标所在的下标位置，然后向后找nums2数组里面第一个比目标值大的值，记录下标，没有就标记-1
优化：建立一个map，将下表和值建立关系
根据值直接找到下标。
法二：
单调栈方法
单调栈
- 单调栈，顾名思义就是栈内元素单调栈底到栈顶按照递增(递减)顺序排列的栈。
- 应用场景：为任意一个元素找左边和右边第一个比自己大/小的位置用单调栈.
- 由于每个元素最多各自进出栈一次,复杂度是O(n).
例如：求解数组中每一个元素i，它的右边第一个比它大的值是多少。
- 此时，倒序遍历
单调栈的基本思路
for(int i=nums2.length;i>=0;i--){ //num2是目标数组
while(!s.empty()&&s.top<=a[i]){
s.pop();
}
res[i]=s.empty()?-1:s.top();
s.push(a[i]);
}
可以用身高进行模拟，更便于理解。
贴一个链接，这位讲的很好
https://leetcode.cn/problems/next-greater-element-i/solution/dan-diao-zhan-jie-jue-next-greater-number-yi-lei-w/
本题代码
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Stack<Integer> stack=new Stack<Integer>();
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>;
int[] res = new int[nums1.length];
for(int num:nums2){
//如果栈不为空且栈顶元素小于当前值，就将栈顶元素pop出去
while(!stack.isEmpty()&&num>stack.peek()){
map.put(stack.pop(),num);
}
stack.push(num);
}
for(int i=0;i< nums1.length;i++)
res[i]=map.getOrDefault(nums1[i],-1);
return res;
}
类似的题
503. 下一个更大元素 II
难度中等620
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例 1:
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
示例 2:
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]
注意的点：
- 这是一个环形数组
- 计算机内部不存在真正的环形数组，所有的环形数组一般都是通过求模的方法达成的
- 这里循环1圈就行。可以想象成【1，2，3】数组变成了【1，2，3，1，2，3】.
class Solution {
public int[] nextGreaterElements(int[] nums) {
Stack<Integer> stack = new Stack<>();
int n = nums.length;
int[] answer = new int[n];
for (int i = n * 2 - 1; i >= 0; i--) {
while (!stack.isEmpty() && stack.peek() <= nums[i % n]) {
stack.pop();
}
answer[i % n] = stack.isEmpty() ? -1 : stack.peek();
stack.push(nums[i % n]);
}
return answer;
}
}
