豆芽网站建设,酷家乐在线设计官网,高端网站鉴赏,微信网站制作系统力扣739.每日温度
题目链接#xff1a;https://leetcode.cn/problems/daily-temperatures/
思路
什么时候用单调栈呢#xff1f;
通常是一维数组#xff0c;要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置#xff0c;此时我们就要想到可以用单调栈了…力扣739.每日温度
题目链接https://leetcode.cn/problems/daily-temperatures/
思路
什么时候用单调栈呢
通常是一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置此时我们就要想到可以用单调栈了。
定义一个单调栈维护的是一个从栈顶到栈底不递减的序列。注意栈里放的是下标判断大小时只要取出对应的数组元素即可。
有三种情况
1遍历元素小于栈顶元素此时是符合栈顶到栈底不递减的规律的将遍历元素压入栈中
2遍历元素等于栈顶元素此时是符合栈顶到栈底不递减的规律的将遍历元素压入栈中
3重点来了遍历元素小于栈顶元素不符合规律了此时用res数组记录两个下标的差值就是第一个比自身温度高的天数了再弹出栈顶元素将遍历元素压入栈中。
这里只需要手动模拟一下就可以理解了。
完整代码
class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] res new int[temperatures.length];DequeInteger stack new LinkedList();stack.push(0);for (int i 1; i temperatures.length; i) {if(temperatures[i] temperatures[stack.peek()]){stack.push(i);}else if(temperatures[i] temperatures[stack.peek()]){stack.push(i);}else{while(!stack.isEmpty() temperatures[i] temperatures[stack.peek()]){res[stack.peek()] i-stack.peek();stack.pop();}stack.push(i);}}return res;}
}力扣496.下一个更大元素1
题目链接https://leetcode.cn/problems/next-greater-element-i/
思路
因为数组里的元素各不相同所以用hashmap来存放元素更容易查找。
此时栈里存放的是nums2的下标。
更多细节需要手动模拟一下比较清楚。特别是找到遍历元素大于栈顶元素的那一段。
完整代码
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int[] res new int[nums1.length];Arrays.fill(res,-1);HashMapInteger,Integer hashmap new HashMap();for (int i 0; i nums1.length; i) {hashmap.put(nums1[i],i);}DequeInteger stack new LinkedList();stack.push(0);for (int i 1; i nums2.length; i) {if(nums2[i] nums2[stack.peek()]){stack.push(i);}else{while (!stack.isEmpty() nums2[i] nums2[stack.peek()]){if(hashmap.containsKey(nums2[stack.peek()])){int index hashmap.get(nums2[stack.peek()]);res[index] nums2[i];}stack.pop();}stack.push(i);}}return res;}
}
