本文主要是介绍代码随想录算法训练营第五十八天 739. 每日温度、 496.下一个更大元素 I,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
代码随想录算法训练营第五十八天 | 739. 每日温度、 496.下一个更大元素 I
739. 每日温度
题目链接:739. 每日温度 - 力扣(LeetCode)
情况一:当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
此时满足递增栈(栈头到栈底的顺序),所以直接入栈。
情况二:当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
如果相等的话,依然直接入栈,因为我们要求的是右边第一个比自己大的元素,而不是大于等于!
情况三:当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
此时如果入栈就不满足递增栈了,这也是找到右边第一个比自己大的元素的时候
class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] answer = new int[temperatures.length];// 单调栈,保持栈中的元素为单调递减// 单调栈装的是元素的索引位置LinkedList<Integer> stack = new LinkedList<>();for(int i = 0; i < answer.length; ++i) {// 判断当前元素与栈顶元素大小while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peekLast()]) {// 若大于栈顶元素,pop栈顶元素且set栈顶元素对应位置到当前元素位置的距离int pre = stack.pollLast();answer[pre] = i - pre; }// 不大于,直接将元素索引添加至栈顶stack.addLast(i);}return answer;}
}
496.下一个更大元素 I
题目链接:496. 下一个更大元素 I - 力扣(LeetCode)
此题就是在739. 每日温度 - 力扣(LeetCode)基础上,多增加了一个nums1作为nums2的子序列
我们依旧使用单调栈来保存nums2中的元素,然后使用map保存nums1的元素,在遍历nums2中元素的同时查找map,看看是否存在
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int len1 = nums1.length;int len2 = nums2.length;int[] ans = new int[len1]; //默认为找不到,所有都为-1Arrays.fill(ans, -1);Map<Integer, Integer> dic = new HashMap<>();// map保存nums1中每个元素的索引位置for(int i = 0; i < len1; ++i) {dic.put(nums1[i], i);}Deque<Integer> stack = new ArrayDeque<>();for(int i = 0; i < len2; ++i) {// 判断当前元素与栈顶元素大小while(!stack.isEmpty() && nums2[stack.peekLast()] < nums2[i]) {// 满足情况三,需要pop栈顶元素直到满足情况一或二int top = nums2[stack.pollLast()];// 判断栈顶元素是否存在于nums1中if(dic.containsKey(top)) {// 若存在,更新nums1元素对应的ans[]ans[dic.get(top)] = nums2[i]; }}stack.offerLast(i);}return ans; }}
总结
使用单调栈主要有三个判断条件。
- 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
- 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
- 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
这篇关于代码随想录算法训练营第五十八天 739. 每日温度、 496.下一个更大元素 I的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!