本文主要是介绍代码随想录算法训练营第五十八天 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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
