廊坊网站排名优化报价,咖啡网站设计建设,钱币网站建设,注册电子邮箱号请根据每日 气温 列表 temperatures #xff0c;重新生成一个列表#xff0c;要求其对应位置的输出为#xff1a;要想观测到更高的气温#xff0c;至少需要等待的天数。如果气温在这之后都不会升高#xff0c;请在该位置用 0 来代替。 输入: temperatures [73,74,75,71,69… 请根据每日 气温 列表 temperatures 重新生成一个列表要求其对应位置的输出为要想观测到更高的气温至少需要等待的天数。如果气温在这之后都不会升高请在该位置用 0 来代替。 输入: temperatures [73,74,75,71,69,72,76,73]输出: [1,1,4,2,1,1,0,0] 每日温度是一道很典型的单调栈的问题就是求下一个最大****下面先列出单调栈的模板
public int[] humdrum3tack(int[] nums) {int n nums.length;// 存放答案的数组int[] res new int[n];StackInteger s new Stack(); // 倒着往栈里放 如果是环状则使用取模运算进行绕环for (int i n - 1; i 0; i--) {// 判定个子高矮while (!s.isEmpty() s.peek() nums[i]) {// 把小于当前元素的栈中元素进行弹栈s.pop();}//如果栈中没元素则后面没有比自己大的值如果有则是栈顶元素res[i] s.isEmpty() ? -1 : s.peek();s.push(nums[i]);}return res;
下面利用图进行说明 单调栈又是什么什么原理呢 入队的时候不断的和栈顶进行比较小于入栈元素的直接进行出栈如果入栈的时候栈为空说明当前元素后面没有比当前元素大的值了
public int[] dailyTemperatures(int[] temperatures) {//对 入参进行判断if(temperaturesnull||temperatures.length0);int ntemperatures.length;StackPair stacknew Stack();//用来维护结果的结果数组int[] resnew int[n];//单调栈一般都是从后往前比遍历for(int in-1;i0;i--){//如果当前栈不为空且栈顶元素小于当前入栈元素直接进行出栈while(!stack.isEmpty()stack.peek().valtemperatures[i]){stack.pop();}//填充结果res[i]stack.isEmpty()?0:stack.peek().index-i;//将当前元素进行入栈stack.push(new Pair(temperatures[i],i));}return res;}class Pair{private int val;private int index;public Pair(int val,int index){this.valval;this.indexindex;}}
