织梦 网站迁移,个人网银登录入口,做网站必须要加v吗,wordpress增加赞赏Day49 力扣单调栈 : 739. 每日温度 #xff5c;496.下一个更大元素 I 739. 每日温度第一印象看完题解的思路什么是单调栈?我的总结 实现中的苦难感悟代码 496.下一个更大元素 I第一印象看完题解的思路实现中的困难感悟代码 739. 每日温度 今天正式开始单调栈#xff0c;这是… Day49 力扣单调栈 : 739. 每日温度 496.下一个更大元素 I 739. 每日温度第一印象看完题解的思路什么是单调栈?我的总结 实现中的苦难感悟代码 496.下一个更大元素 I第一印象看完题解的思路实现中的困难感悟代码 739. 每日温度 今天正式开始单调栈这是单调栈一篇扫盲题目也是经典题。 大家可以读题思考暴力的解法然后在看单调栈的解法。 就能感受出单调栈的巧妙 https://programmercarl.com/0739.%E6%AF%8F%E6%97%A5%E6%B8%A9%E5%BA%A6.html 第一印象
暴力解法还是比较好想的
class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] answer new int[temperatures.length];for (int i 0; i answer.length; i) {int curTemp temperatures[i];int day 1;//flag 0代表没有更高的那天1代表有更高的那天int flag 0;for (int j i 1; j temperatures.length; j) {if (temperatures[j] curTemp) {answer[i] day;flag 1;break;} else {day;}}if (flag 0) answer[i] 0;}return answer;}
}当然直接超时了下面学习单调栈。
看完题解的思路
我看完单调栈的工作过程了, 太tm神奇了.
什么是单调栈?
单调栈就是用于找一个元素左 / 右第一个比自己大 / 小的元素的题目。
单调栈的本质是空间换时间, 更直白来说就是用一个栈来记录我们遍历过的元素因为我们遍历数组的时候我们不知道之前都遍历了哪些元素以至于遍历一个元素找不到是不是之前遍历过一个更小的所以我们需要用一个容器这里用单调栈来记录我们遍历过的元素。
在使用单调栈的时候首先要明确如下几点
1.单调栈里存放的元素是什么
单调栈里只需要存放元素的下标i就可以了如果需要使用对应的元素直接T[i]就可以获取。
2.单调栈里元素是递增呢 还是递减呢
注意以下讲解中顺序的描述为 从栈头到栈底的顺序因为单纯的说从左到右或者从前到后不说栈头朝哪个方向的话大家一定比较懵。
这道题我们要让栈里的元素是递增的 (从栈头到栈底)
对于数组我们从左到右遍历, 每次拿来的元素 i 都是遍历过的元素的右面的. 这就实现了找右面更大 / 更小的元素.
而栈里, 我们让元素都是递增的. 这样每次拿来元素 i ,就是 栈顶元素右侧第一个比栈顶元素大的. 这里会产生一个疑问: 比如栈里是 69 71. 71 不是比栈顶元素 69 大吗?
是的, 但 71 是 69 左侧的元素. 因为数组遍历顺序是从左到右, 然后压入栈. 所以越靠近栈头的元素在数组里越靠右, 栈尾则靠左.
那如果拿来的元素 i 比栈顶元素更小呢? 那压入栈就可以了. 栈递增所以栈顶元素就是栈里最小的, 拿到的元素 i 比最小的还要小, 所以不会比栈内任何元素大, 就说明还没找到这些元素右侧第一个更大的.
我的总结
所以求右侧第一个更大元素时, 为什么让栈内元素递增?
因为栈内元素递增, 栈头元素就是最小的那个. 因为数组从左到右遍历, 栈头元素是右侧的, 栈底元素是左侧的.
每次拿来元素 i 和栈头元素比较, 没有栈头大就没有任何栈内元素大, 就压入栈.
元素 i 比栈头元素大, 就找到了栈头元素右侧第一个更大. 记录结果, 弹出栈头元素. 当然也要用元素 i 继续和新栈头元素比较, 直到元素 i 比新栈头元素小而压入栈, 或者栈空了元素 i 就压入栈.
那么如果找右侧第一个更小, 就应该让栈内元素递减了.
每次其实只有三种操作:
元素 i 比栈头元素大元素 i 比栈头元素小元素 i 和栈头元素相等
只要分别写出三中操作的代码, 就写完这道题了. 用这三种操作控制栈内元素是递增的, 就可以了.
实现中的苦难
思路清晰没有困难
int index stack.pop();
answer[index] i - index;记录结果的时候要注意别岔劈了.
感悟
具体的图解模拟过程, 到代码随想录里看一下吧.
第一次看完视频感觉单调栈很神奇, 甚至有点不知道为什么会产生这种效果.
我觉得多做做题就理解了, 而且这个也挺套路的.
代码
class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] answer new int[temperatures.length];//声明单调栈 空间换时间DequeInteger stacknew LinkedList();//先把第一个元素加入栈里stack.push(0);for (int i 1; i temperatures.length; i) {//元素 i 比栈顶元素小 或相等 都应该压入if (temperatures[i] temperatures[stack.peek()]) {stack.push(i);} else {//如果元素i比栈顶元素大,就要记录结果并弹出栈顶, 继续比较,直到没有栈顶元素大while (!stack.isEmpty() temperatures[i] temperatures[stack.peek()]) {int index stack.pop();answer[index] i - index;}stack.push(i);}}return answer;}
}496.下一个更大元素 I 本题和 739. 每日温度 看似差不多其实 有加了点难度。 https://programmercarl.com/0496.%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E5%85%83%E7%B4%A0I.html 第一印象
试了试,我有点迷糊.
看题解吧, 我真绕进去了.
我写的 num1 的元素 在 num2 中的位置是这么写的, 但卡哥说要用 map.
for (int i 0; i nums1.length; i) {//num1里当前的元素int cur nums1[i];int indexInNum2 -1;//找到当前元素在num2里的下标for (int j 0; j nums2.length; j) {if (nums2[j] cur) {indexInNum2 j;}}}看完题解的思路
先用 map 记录 num1 中元素的值和下标,值为Key,下标为value
这样我们就可以只对 num2 做经典的单调栈操作, 如果我要pop的那个下标在map里, 就要记录结果. //如果拿来的元素 i 比栈顶元素更大, 持续比较while (!stack.isEmpty() nums2[i] nums2[stack.peek()]) {int index stack.pop();int cur nums2[index];//如果弹出的元素是在map里的(nums1里的),就要记录结果//如果不是nums1里的,只弹出就可以了if (map.containsKey(cur)) {//res[在nums1里的下标] 下一个更大的数值.res[map.get(cur)] nums2[i];}}//拿来的元素 i 在比较之后, 一定要push进栈.stack.push(i);就是比较绕, 一会是下标, 一会是元素.
每日温度是, 对于 每一个找到了更大的元素都 pop并记录结果到result里.
这道题是, 对于每一个找到了更大的元素都pop, 但只有在nums1(在map)里的才记录到结果result里.
实现中的困难
没有
感悟
用map来不被绕进去, 解决单调栈套的这个壳子.
还是实现能力不够啊
代码
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {HashMapInteger, Integer map new HashMap();//num1中值为Key, 下标为Valuefor (int i 0; i nums1.length; i) {map.put(nums1[i], i);}int[] res new int[nums1.length];DequeInteger stack new LinkedList();//先都初始化为 -1.Arrays.fill(res, -1);stack.push(0);for (int i 1; i nums2.length; i) {if (nums2[i] nums2[stack.peek()]) {stack.push(i);} else {//如果拿来的元素 i 比栈顶元素更大, 持续比较while (!stack.isEmpty() nums2[i] nums2[stack.peek()]) {int index stack.pop();int cur nums2[index];//如果弹出的元素是在map里的(nums1里的),就要记录结果//如果不是nums1里的,只弹出就可以了if (map.containsKey(cur)) {//res[在nums1里的下标] 下一个更大的数值.res[map.get(cur)] nums2[i];}}//拿来的元素 i 在比较之后, 一定要push进栈.stack.push(i);}}return res;}
}
