每日一题
今天刷到了一道用到单调栈来解决的题目,想到自己没有总结过单调栈的知识点,因此想总结一下。
介绍
什么是单调栈?
单调栈的定义其实很简单,所谓单调栈就是指一个单调递增或是单调递减的栈。
那单调栈有什么用呢?
单调栈通常用来在一串数字(例如数组)中,找到某个数字的左侧或是右侧最近的大于或小于这个数字的数。
那么是如何实现的呢?
如果想要在一个数组中找到一个数字右侧大于它本身的第一个数,就可以使用一个单调递增的栈来实现。
可以从后向前遍历该数组,,如果此时单调栈为空那么将该数字压入栈,如果栈中不为空且当前遍历到数大于栈顶的数字,那么就会将栈顶的数字弹出栈,如果栈中的数一直小那就一直弹出,因为我们要维护这个从上到下递增的栈。这样对于每一个数来说,当轮到这个数的时候,在判断栈顶数字并弹出后,如果弹出后栈为空,那就证明这个数字后没有它本身大的数字。如果栈中还有数字,那么栈顶的元素就是该数字右侧第一个比他大的数字。因为比他的数字不会被弹出,并且遍历从后向前,这个数字一定是右侧最近的。
这个情况说完后,其他的情况也是一样的。
例题
来看力扣496题——下一个最大元素。
题目要求
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 。
题目解析
该题是要我们找到一个数组num2的子数组num1中的数在num2中右侧最近的一个大于它的数,如果不存在就返回-1,存在就保存这个数,最后将这些数放在数组中。这个一个典型的单调栈问题,我们可以通过我上面提到的方法找到num2数组中的每个数右侧第一个大于本身的数并将其存在一个map中,最后通过遍历num1数组在map中找到对应的数字并存入数组。
下面我们来图文解释一下示例1中的情况
首先遍历数组,第一个数字——2,目前栈是空的,得到-1.将2压入栈
下面是4,2小于4.因此将2弹出,此时栈空得到-1,压入4
下面轮到3,3小于4,因此没有弹出操作,得到4,将3也压入栈
最后轮到1,1也小于3,因此不会弹出,得到3,并将1压入栈。
至此遍历结束我们得到了全部的数据并将其存入map中
1—— 3
3—— 4
4—— -1
2—— -1
最后遍历num1数组,拿到结果[-1,3,-1]
代码实现
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer,Integer> map = new HashMap<>();
Deque<Integer> stack = new ArrayDeque<Integer>();
for(int i =nums2.length-1;i>=0;i--){
int num = nums2[i];
while(!stack.isEmpty()&&num>=stack.peek()){
stack.pop();
}
if(stack.isEmpty()){
map.put(num,-1);
}else{
map.put(num,stack.peek());
}
stack.push(num);
}
int[] res = new int[nums1.length];
for(int i=0;i<nums1.length;i++){
res[i] = map.get(nums1[i]);
}
return res;
}
}
结果