可以做代销的网站,爱南宁app下载官网,wordpress主机模板,营销型类型网站多少钱些1、题目描述
【题目链接】 给定一个整数数组 temperatures #xff0c;表示每天的温度#xff0c;返回一个数组 answer #xff0c;其中 answer[i] 是指对于第 i 天#xff0c;下一个更高温度出现在几天后。如果气温在这之后都不会升高#xff0c;请在该位置用 0 来代替。…1、题目描述
【题目链接】 给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。
示例 1: 输入: temperatures [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]
示例 2: 输入: temperatures [30,40,50,60] 输出: [1,1,1,0]
示例 3: 输入: temperatures [30,60,90] 输出: [1,1,0]
提示 1 temperatures.length 105 30 temperatures[i] 100
2、基本思路 如果采用最简单最暴力的方法就是从当前位置i的下一个位置i1出发找到第一个j使得temperatures[j] temperatures[i]这种方法最坏情况得时间复杂度为O(n^2)。那么有没有更好得方法呢答案是有的。 采用单调栈的方法维护一个从栈底到栈顶单调递减的序列举个简单的例子例如温度序列为【14355236】
初始化栈空首先栈空1入栈栈中元素[1];第二个数4与栈顶元素1比较14则出栈且答案为res[1]1栈空结束比较4入栈栈中元素[4]第三个数3与栈顶元素4比较433入栈栈中元素[4,3]第四个数5与栈顶元素3比较353出栈答案为res[3]1栈中元素[4]栈非空继续与栈顶元素比较454出战答案为res[2]2栈中元素[]栈空5入栈栈中元素[5]第五个元素5与栈顶元素5比较555入栈栈中元素[55]第六个元素2与栈顶元素5比较522入栈栈中元素[552]第七个元素3与栈顶元素2比较232出栈且答案为res[6]1栈中元素[55]栈非空,继续与栈顶元素5比较533入栈栈中元素[553]第八个元素6与栈顶元素3比较363出栈且答案为res[7]1栈中元素[55]栈非空与栈顶元素5比较565出栈且答案为res[4]4栈中元素[5]栈非空与栈顶元素5比较565出栈且答案为res[5]3栈中元素[]栈为空且序列遍历结束 最终答案为[1,2,1,4,3,1,1,0] 同样我们也可以维护一个从栈底到栈顶维护一个单调递减的序列遍历的序列从右往左。
单调栈的基本思想——及时去掉无用的数据保证栈中数据有序
3、代码实现
方法一
vectorint solve1(vectorint temperatures)
{int n temperatures.size();vectorint res(n,0);stackint st;for(int i 0;in;i){int t temperatures[i];while(!st.empty() t temperatures[st.top()]){res[st.top()] i-st.top();st.pop() ;}st.push(i);}return res;}方法二
vectorint solve(vectorint temperatures)
{int n temperatures.size();vectorint res(n,0);stackint st;for(int i n-1;i0;i--){int t temperatures[i];while(!st.empty() ttemperatures[st.top()]){st.pop();}if(!st.empty()){res[i] st.top()-i;}st.push(i);}return res;}
