网站建设的发展目标,app推广赚佣金,宁波seo关键词优化,简历自我评价随想录日记part45 t i m e #xff1a; time#xff1a; time#xff1a; 2024.04.17 主要内容#xff1a;今天开始要学习单调栈的相关知识了#xff0c;今天的内容主要涉及#xff1a;每日温度 #xff1b;下一个更大元素 I
739. 每日温度 496.下一个更大元素 I Topic…随想录日记part45 t i m e time time 2024.04.17 主要内容今天开始要学习单调栈的相关知识了今天的内容主要涉及每日温度 下一个更大元素 I
739. 每日温度 496.下一个更大元素 I Topic1每日温度
题目
思路 通常是一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置此时我们就要想到可以用单调栈了。 用一个栈来记录我们遍历过的元素因为我们遍历数组的时候我们不知道之前都遍历了哪些元素以至于遍历一个元素找不到是不是之前遍历过一个更小的所以我们需要用一个容器这里用单调栈来记录我们遍历过的元素。 在使用单调栈的时候首先要明确如下几点 1.单调栈里存放的元素是什么 单调栈里只需要存放元素的下标i就可以了如果需要使用对应的元素直接T[i]就可以获取。 2.单调栈里元素是递增呢 还是递减呢 注意以下讲解中顺序的描述为 从栈头到栈底的顺序 如果求一个元素右边第一个更大元素单调栈就是递增的如果求一个元素右边第一个更小元素单调栈就是递减的。 文字描述理解起来有点费劲接下来我画了一系列的图来讲解单调栈的工作过程大家再去思考本题为什么是递增栈。 使用单调栈主要有三个判断条件。 当前遍历的元素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]: 1.首先先将第一个遍历元素加入单调栈: 加入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数组也更新完了。 代码实现如下 import java.util.Stack;class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] result new int[temperatures.length];StackInteger stack new Stack();stack.push(0);for (int i 1; i temperatures.length; i) {if (temperatures[i] temperatures[stack.peek()]) {stack.push(i);} else {while (!stack.isEmpty() temperatures[i] temperatures[stack.peek()]) {result[stack.peek()] i - stack.peek();stack.pop();}stack.push(i);}}return result;}
}时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n) Topic2下一个更大元素 I 思路 接下来就要分析如下三种情况一定要分析清楚。 情况一当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况 此时满足递增栈栈头到栈底的顺序所以直接入栈。 情况二当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况 如果相等的话依然直接入栈因为我们要求的是右边第一个比自己大的元素而不是大于等于 情况三当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况 此时如果入栈就不满足递增栈了这也是找到右边第一个比自己大的元素的时候。 判断栈顶元素是否在nums1里出现过注意栈里的元素是nums2的元素如果出现过开始记录结果。 记录结果这块逻辑有一点小绕要清楚此时栈顶元素在nums2数组中右面第一个大的元素是nums2[i]即当前遍历元素。 class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int[] result new int[nums1.length];Arrays.fill(result, -1);StackInteger stack new Stack();HashMapInteger, Integer umap new HashMap(); // key:下标元素value下标for (int i 0; i nums1.length; i) {umap.put(nums1[i], i);}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 (umap.containsKey(nums2[stack.peek()])) {Integer index umap.get(nums2[stack.peek()]);result[index] nums2[i];}stack.pop();}stack.push(i);}}return result;}
}时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n)
