济南网络公司建站,网站推广网络推广,优秀企业网站,网站建设维护面试文章目录 Day58 每日温度题目思路代码 下一个更大元素 I题目思路代码 Day58 每日温度
739. 每日温度 - 力扣#xff08;LeetCode#xff09;
题目
请根据每日 气温 列表#xff0c;重新生成一个列表。对应位置的输出为#xff1a;要想观测到更高的气温#xff0c;至少需… 文章目录 Day58 每日温度题目思路代码 下一个更大元素 I题目思路代码 Day58 每日温度
739. 每日温度 - 力扣LeetCode
题目
请根据每日 气温 列表重新生成一个列表。对应位置的输出为要想观测到更高的气温至少需要等待的天数。如果气温在这之后都不会升高请在该位置用 0 来代替。
例如给定一个列表 temperatures [73, 74, 75, 71, 69, 72, 76, 73]你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度都是在 [30, 100] 范围内的整数。
思路
我怎么能想到用单调栈呢 什么时候用单调栈呢
通常是一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置此时我们就要想到可以用单调栈了。时间复杂度为O(n)。
例如本题其实就是找找到一个元素右边第一个比自己大的元素此时就应该想到用单调栈了。
在使用单调栈的时候首先要明确如下几点
单调栈里存放的元素是什么
单调栈里只需要存放元素的下标i就可以了如果需要使用对应的元素直接T[i]就可以获取。
单调栈里元素是递增呢 还是递减呢
注意以下讲解中顺序的描述为 从栈头到栈底的顺序因为单纯的说从左到右或者从前到后
如果求一个元素右边第一个更大元素单调栈就是递增的如果求一个元素右边第一个更小元素单调栈就是递减的。
使用单调栈主要有三个判断条件。
当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
把这三种情况分析清楚了也就理解透彻了。
代码
class Solution {public int[] dailyTemperatures(int[] temperatures) {/**如果求一个元素右边第一个更大元素单调栈就是递增的如果求一个元素右边第一个更小元素单调栈就是递减的。本题是求一个元素右边第一个更大元素单调栈递增*/LinkedListInteger stack new LinkedListInteger();stack.push(0);int res[] new int[temperatures.length];for(int i 1; i temperatures.length; i){int position stack.peek();if (temperatures[position] temperatures[i]){stack.push(i);} else if (temperatures[position] temperatures[i]){stack.push(i);} else {while(!stack.isEmpty() temperatures[stack.peek()] temperatures[i]){res[stack.peek()] i - stack.peek();stack.pop();}stack.push(i);}}return res;}
}下一个更大元素 I
496. 下一个更大元素 I - 力扣LeetCode
题目
给你两个 没有重复元素 的数组 nums1 和 nums2 其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在对应位置输出 -1 。
示例 1:
输入: nums1 [4,1,2], nums2 [1,3,4,2]. 输出: [-1,3,-1] 解释: 对于 num1 中的数字 4 你无法在第二个数组中找到下一个更大的数字因此输出 -1 。 对于 num1 中的数字 1 第二个数组中数字1右边的下一个较大数字是 3 。 对于 num1 中的数字 2 第二个数组中没有下一个更大的数字因此输出 -1 。
示例 2: 输入: nums1 [2,4], nums2 [1,2,3,4]. 输出: [3,-1] 解释: 对于 num1 中的数字 2 第二个数组中的下一个较大数字是 3 。 对于 num1 中的数字 4 第二个数组中没有下一个更大的数字因此输出-1 。
提示
1 nums1.length nums2.length 10000 nums1[i], nums2[i] 10^4nums1和nums2中所有整数 互不相同nums1 中的所有整数同样出现在 nums2 中
思路
从题目示例中我们可以看出最后是要求nums1的每个元素在nums2中下一个比当前元素大的元素那么就要定义一个和nums1一样大小的数组result来存放结果。
这么定义这个result数组初始化应该为多少呢
题目说如果不存在对应位置就输出 -1 所以result数组如果某位置没有被赋值那么就应该是是-1所以就初始化为-1。
在遍历nums2的过程中我们要判断nums2[i]是否在nums1中出现过因为最后是要根据nums1元素的下标来更新result数组。
注意题目中说是两个没有重复元素 的数组 nums1 和 nums2。
使用单调栈首先要想单调栈是从大到小还是从小到大。
本题和739. 每日温度是一样的。
栈头到栈底的顺序要从小到大也就是保持栈里的元素为递增顺序。只要保持递增才能找到右边第一个比自己大的元素。
可能这里有一些同学不理解那么可以自己尝试一下用递减栈能不能求出来。其实递减栈就是求右边第一个比自己小的元素了。
接下来就要分析如下三种情况一定要分析清楚。
情况一当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
此时满足递增栈栈头到栈底的顺序所以直接入栈。
情况二当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
如果相等的话依然直接入栈因为我们要求的是右边第一个比自己大的元素而不是大于等于
情况三当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
此时如果入栈就不满足递增栈了这也是找到右边第一个比自己大的元素的时候。
判断栈顶元素是否在nums1里出现过注意栈里的元素是nums2的元素如果出现过开始记录结果。
记录结果这块逻辑有一点小绕要清楚此时栈顶元素在nums2数组中右面第一个大的元素是nums2[i]即当前遍历元素。
while(!stack.isEmpty() nums2[stack.peek()] nums2[i]){if (map.containsKey(nums2[stack.peek()])){Integer index map.get(nums2[stack.peek()]);res[index] nums2[i];}stack.pop();
}
stack.push(i);代码
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {MapInteger, Integer map new HashMap();LinkedListInteger stack new LinkedList();for(int i 0; i nums1.length; i) map.put(nums1[i], i);int res[] new int[nums1.length];Arrays.fill(res, -1);stack.push(0);for(int i 1; i nums2.length; i){int position stack.peek();if (nums2[position] nums2[i]){stack.push(i);}else{while(!stack.isEmpty() nums2[stack.peek()] nums2[i]){if (map.containsKey(nums2[stack.peek()])){Integer index map.get(nums2[stack.peek()]);res[index] nums2[i];}stack.pop();}stack.push(i);}}return res;}
}
