网站建设公司推荐万维科技,国内十大搜索引擎网站,新冠北京最新消息,网站建设数据库选择代码随想录算法训练营第五十八天 | 739. 每日温度#xff0c;496.下一个更大元素 I 739. 每日温度496.下一个更大元素 I 739. 每日温度
题目链接 视频讲解 给定一个整数数组 temperatures #xff0c;表示每天的温度#xff0c;返回一个数组 answer #xff0c;其中 answe… 代码随想录算法训练营第五十八天 | 739. 每日温度496.下一个更大元素 I 739. 每日温度496.下一个更大元素 I 739. 每日温度
题目链接 视频讲解 给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后如果气温在这之后都不会升高请在该位置用 0 来代替
输入: temperatures [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]怎么能想到用单调栈呢 什么时候用单调栈呢 通常是一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置此时我们就要想到可以用单调栈了时间复杂度为O(n) 例如本题其实就是找找到一个元素右边第一个比自己大的元素此时就应该想到用单调栈了 那么单调栈的原理是什么呢为什么时间复杂度是O(n)就可以找到每一个元素的右边第一个比它大的元素位置呢 单调栈的本质是空间换时间因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素优点是整个数组只需要遍历一次 更直白来说就是用一个栈来记录我们遍历过的元素因为我们遍历数组的时候我们不知道之前都遍历了哪些元素以至于遍历一个元素找不到是不是之前遍历过一个更小的所以我们需要用一个容器这里用单调栈来记录我们遍历过的元素 在使用单调栈的时候首先要明确如下几点 单调栈里存放的元素是什么 单调栈里只需要存放元素的下标i就可以了如果需要使用对应的元素直接T[i]就可以获取 单调栈里元素是递增呢 还是递减呢 注意以下讲解中顺序的描述为 从栈头到栈底的顺序因为单纯的说从左到右或者从前到后不说栈头朝哪个方向的话一定比较懵 这里我们要使用递增循序再强调一下是指从栈头到栈底的顺序因为只有递增的时候栈里要加入一个元素i的时候才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i 即如果求一个元素右边第一个更大元素单调栈就是递增的如果求一个元素右边第一个更小元素单调栈就是递减的 文字描述理解起来有点费劲接下来用一系列的图来讲解单调栈的工作过程再去思考本题为什么是递增栈 使用单调栈主要有三个判断条件 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况 把这三种情况分析清楚了也就理解透彻了 接下来用temperatures [73, 74, 75, 71, 71, 72, 76, 73]为例来逐步分析输出应该是 [1, 1, 4, 2, 1, 1, 0, 0] 首先先将第一个遍历元素加入单调栈 加入T[1] 74因为T[1] T[0]当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况 要保持一个递增单调栈从栈头到栈底所以将T[0]弹出T[1]加入此时result数组可以记录了result[0] 1即T[0]右面第一个比T[0]大的元素是T[1] 加入T[2]同理T[1]弹出 加入T[3]T[3] T[2] 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况加T[3]加入单调栈 加入T[4]T[4] T[3] 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况此时依然要加入栈不用计算距离因为我们要求的是右面第一个大于本元素的位置而不是大于等于 加入T[5]T[5] T[4] 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况将T[4]弹出同时计算距离更新result T[4]弹出之后 T[5] T[3] 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况将T[3]继续弹出同时计算距离更新result 直到发现T[5]小于T[st.top()]终止弹出将T[5]加入单调栈 加入T[6]同理需要将栈里的T[5]T[2]弹出 同理继续弹出 此时栈里只剩下了T[6] 加入T[7] T[7] T[6] 直接入栈这就是最后的情况result数组也更新完了 此时有可能就疑惑了那result[6] , result[7]怎么没更新啊元素也一直在栈里 其实定义result数组的时候就应该直接初始化为0如果result没有更新说明这个元素右面没有更大的了也就是为0 以上在图解的时候已经把这三种情况都做了详细的分析 情况一当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况 情况二当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况 情况三当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况 通过以上过程大家可以自己再模拟一遍就会发现只有单调栈递增从栈口到栈底顺序就是求右边第一个比自己大的单调栈递减的话就是求右边第一个比自己小的
class Solution {
public:vectorint dailyTemperatures(vectorint T) {// 递增栈stackint st;vectorint result(T.size(), 0);st.push(0);for (int i 1; i T.size(); i) {if (T[i] T[st.top()]) { // 情况一st.push(i);} else if (T[i] T[st.top()]) { // 情况二st.push(i);} else {while (!st.empty() T[i] T[st.top()]) { // 情况三result[st.top()] i - st.top();st.pop();}st.push(i);}}return result;}
};496.下一个更大元素 I
题目链接 视频讲解 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] 是如上所述的 下一个更大元素
输入nums1 [4,1,2], nums2 [1,3,4,2].
输出[-1,3,-1]在739. 每日温度中是求每个元素下一个比当前元素大的元素的位置 本题则是说nums1 是 nums2的子集找nums1中的元素在nums2中下一个比当前元素大的元素 看上去和739. 每日温度就如出一辙了 几乎是一样的但是这么绕了一下其实还上升了一点难度 需要对单调栈使用的更熟练一些才能顺利的把本题写出来 从题目示例中我们可以看出最后是要求nums1的每个元素在nums2中下一个比当前元素大的元素那么就要定义一个和nums1一样大小的数组result来存放结果 一些人可能看到两个数组都已经懵了不知道要定一个一个多大的result数组来存放结果了 这么定义这个result数组初始化应该为多少呢 题目说如果不存在对应位置就输出 -1 所以result数组如果某位置没有被赋值那么就应该是是-1所以就初始化为-1 在遍历nums2的过程中我们要判断nums2[i]是否在nums1中出现过因为最后是要根据nums1元素的下标来更新result数组 注意题目中说是两个没有重复元素 的数组 nums1 和 nums2 没有重复元素我们就可以用map来做映射了。根据数值快速找到下标还可以判断nums2[i]是否在nums1中出现过 C中当我们要使用集合来解决哈希问题的时候优先使用unordered_set因为它的查询和增删效率是最优的 那么预处理代码如下:
unordered_mapint, int umap; // key:下标元素value下标
for (int i 0; i nums1.size(); i) {umap[nums1[i]] i;
}使用单调栈首先要想单调栈是从大到小还是从小到大 本题和739. 每日温度是一样的 栈头到栈底的顺序要从小到大也就是保持栈里的元素为递增顺序。只要保持递增才能找到右边第一个比自己大的元素 可能这里有一些人不理解那么可以自己尝试一下用递减栈能不能求出来。其实递减栈就是求右边第一个比自己小的元素了 接下来就要分析如下三种情况一定要分析清楚 情况一当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况 此时满足递增栈栈头到栈底的顺序所以直接入栈 情况二当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况 如果相等的话依然直接入栈因为我们要求的是右边第一个比自己大的元素而不是大于等于 情况三当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况 此时如果入栈就不满足递增栈了这也是找到右边第一个比自己大的元素的时候 判断栈顶元素是否在nums1里出现过注意栈里的元素是nums2的元素如果出现过开始记录结果 记录结果这块逻辑有一点小绕要清楚此时栈顶元素在nums2数组中右面第一个大的元素是nums2[i]即当前遍历元素 代码如下
while (!st.empty() nums2[i] nums2[st.top()]) {if (umap.count(nums2[st.top()]) 0) { // 看map里是否存在这个元素int index umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标result[index] nums2[i];}st.pop();
}
st.push(i);class Solution {
public:vectorint nextGreaterElement(vectorint nums1, vectorint nums2) {stackint st;vectorint result(nums1.size(), -1);if (nums1.size() 0) return result;unordered_mapint, int umap; // key:下标元素value下标for (int i 0; i nums1.size(); i) {umap[nums1[i]] i;}st.push(0);for (int i 1; i nums2.size(); i) {if (nums2[i] nums2[st.top()]) { // 情况一st.push(i);} else if (nums2[i] nums2[st.top()]) { // 情况二st.push(i);} else { // 情况三while (!st.empty() nums2[i] nums2[st.top()]) {if (umap.count(nums2[st.top()]) 0) { // 看map里是否存在这个元素int index umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标result[index] nums2[i];}st.pop();}st.push(i);}}return result;}
};
