可以自己设计一个公司的网站,牛商网建设的食品网站,wordpress mega,网站推广的营销策划方案#x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;练题 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录 每日温度下一个更大元素 I总… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接练题 长路漫漫浩浩万事皆有期待 文章目录 每日温度下一个更大元素 I总结 每日温度
739. 每日温度 - 力扣LeetCode
给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。
单调栈的本质是空间换时间因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素优点是整个数组只需要遍历一次。
更直白来说就是用一个栈来记录我们遍历过的元素因为我们遍历数组的时候我们不知道之前都遍历了哪些元素以至于遍历一个元素找不到是不是之前遍历过一个更小的所以我们需要用一个容器这里用单调栈来记录我们遍历过的元素。
在使用单调栈的时候首先要明确如下几点
单调栈里存放的元素是什么 单调栈里只需要存放元素的下标i就可以了如果需要使用对应的元素直接T[i]就可以获取。
单调栈里元素是递增呢 还是递减呢 这里我们要使用递增循序再强调一下是指从栈头到栈底的顺序因为只有递增的时候栈里要加入一个元素i的时候才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。
即如果求一个元素右边第一个更大元素单调栈就是递增的如果求一个元素右边第一个更小元素单调栈就是递减的。
使用单调栈主要有三个判断条件。 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况 把这三种情况分析清楚了也就理解透彻了。
class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] result new int[temperatures.length];Arrays.fill(result, 0);StackInteger st new Stack();st.push(0);for (int i 1; i temperatures.length; i) {if (temperatures[i] temperatures[st.peek()]) {st.push(i);} else {while (!st.isEmpty()temperatures[i] temperatures[st.peek()]) {result[st.peek()] i - st.pop();}st.push(i);}}return result;}
}下一个更大元素 I
496. 下一个更大元素 I - 力扣LeetCode
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] 是如上所述的 下一个更大元素 。
这么定义这个result数组初始化应该为多少呢
题目说如果不存在对应位置就输出 -1 所以result数组如果某位置没有被赋值那么就应该是是-1所以就初始化为-1。
在遍历nums2的过程中我们要判断nums2[i]是否在nums1中出现过因为最后是要根据nums1元素的下标来更新result数组。
注意题目中说是两个没有重复元素 的数组 nums1 和 nums2。
没有重复元素我们就可以用map来做映射了。根据数值快速找到下标还可以判断nums2[i]是否在nums1中出现过。
栈头到栈底的顺序要从小到大也就是保持栈里的元素为递增顺序。只要保持递增才能找到右边第一个比自己大的元素。
可能这里有一些同学不理解那么可以自己尝试一下用递减栈能不能求出来。其实递减栈就是求右边第一个比自己小的元素了。
接下来就要分析如下三种情况一定要分析清楚。
情况一当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况 此时满足递增栈栈头到栈底的顺序所以直接入栈。
情况二当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况 如果相等的话依然直接入栈因为我们要求的是右边第一个比自己大的元素而不是大于等于
情况三当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况 此时如果入栈就不满足递增栈了这也是找到右边第一个比自己大的元素的时候。
判断栈顶元素是否在nums1里出现过注意栈里的元素是nums2的元素如果出现过开始记录结果。
class Solution {public static int[] nextGreaterElement(int[] nums1, int[] nums2) {StackInteger st new Stack();HashMapInteger, Integer map new HashMap();int[] result new int[nums1.length];for (int i 0; i nums2.length; i) {map.put(nums2[i], -1);}st.push(0);for (int i 1; i nums2.length; i) {while (!st.isEmpty()nums2[i]nums2[st.peek()]){map.put(nums2[st.pop()],nums2[i]);}st.push(i);}for (int i 0; i nums1.length; i) {result[i] map.get(nums1[i]);}return result;}
}总结
今天我们完成了每日温度、下一个更大元素 I两道题相关的思想需要多复习回顾。接下来我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
