买网站名称,微信网站平台怎么建立,做网站建设一年能赚多少,昆明网站建设frf739. 每日温度
思路
首先想到的当然是暴力解法#xff0c;两层for循环#xff0c;把至少需要等待的天数就搜出来了。时间复杂度是O(n^2)
那么接下来在来看看使用单调栈的解法。 什么时候用单调栈呢#xff1f;
通常是一维数组#xff0c;要寻找任一个元素的右边或者左边…739. 每日温度
思路
首先想到的当然是暴力解法两层for循环把至少需要等待的天数就搜出来了。时间复杂度是O(n^2)
那么接下来在来看看使用单调栈的解法。 什么时候用单调栈呢
通常是一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置此时我们就要想到可以用单调栈了。时间复杂度为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 int[] dailyTemperatures(int[] temperatures) {int[] answer new int[temperatures.length];//小的话一直压栈记录大的话就下表相减求距离/**如果当前遍历的元素 大于栈顶元素表示 栈顶元素的 右边的最大的元素就是 当前遍历的元素所以弹出 栈顶元素并记录如果栈不空的话还要考虑新的栈顶与当前元素的大小关系否则的话可以直接入栈。注意单调栈里 加入的元素是 下标。*/StackInteger st new Stack();st.push(0);for (int i 1; i temperatures.length; i) {if (temperatures[i] temperatures[st.peek()]){//如果当前元素大于栈顶元素//遍历栈如果碰到当前元素小于等于栈顶元素时将当前元素的下标放入栈中//如果当前元素大于栈顶元素栈顶元素为下标的值为 i- st.popwhile (!st.isEmpty() temperatures[i] temperatures[st.peek()]){if (temperatures[i] temperatures[st.peek()]){int stIndex st.pop();answer[stIndex] i - stIndex;}}st.push(i);}else {//当前元素小于等于栈顶元素st.push(i);}}return answer;}
} 496.下一个更大元素 I
思路
这题秒了基本没看卡哥的题解但思路基本也是与卡哥的一致。但需要注意的细节点是每次 i 遍历完之后需要对栈stack 进行清空处理防止本次遗留元素影响到下一次层的循环中。
并且我将结果数组 res[] 均初始化为了-1具体思路见代码
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {//nums1 是 nums2 的子集int[] res new int[nums1.length];Arrays.fill(res,-1);StackInteger st new Stack();//找出num1[i] num2[j]的j 值for (int i 0; i nums1.length; i) {for (int j 0; j nums2.length; j) {if (nums1[i] nums2[j]){//确定 nums2[j] 的 下一个更大元素st.push(j);}if (!st.isEmpty() nums2[j] nums2[st.peek()]){res[i] nums2[j];st.pop();}}st.clear();}return res;}
}
