1.每日温度题（一道关于栈的问题）
请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
输入:temperatures= [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]
解题思路：创建一个栈用于存数组的下标，存储的是值递减，表示存储的下标还没找到比他温度高的，如果一直没找到，就用创建的数组默认值0；
package com.chenghaixiang.jianzhi2.day12;
import java.util.ArrayDeque;
import java.util.Deque;
/**
* @author 程海翔
* @school 石家庄铁道大学
*/
public class Office038 {
}
//请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
class Solution02 {
public int[] dailyTemperatures(int[] temperatures) {
int[] res=new int[temperatures.length];
// 创建一个单调栈
Deque<Integer> stack=new ArrayDeque<>();
int i=0;
while (i<temperatures.length){
// 当栈为空，或者当前元素 <= 栈顶元素，则将当前元素的索引进栈，形成栈底到栈顶的递减栈
// 同时，将 i 指向下一天的温度
if(stack.isEmpty()||temperatures[stack.peek()]>=temperatures[i]){
//栈中存取的是temperatures中温度所在的下标
stack.push(i++);
}else {
// 如果当前元素 > 栈顶元素，则将栈顶索引出栈，说明找到了比栈顶索引更高的温度，栈顶元素下标对应的地方获取对应的天数。
Integer top=stack.pop();
res[top]=i-top;
}
}
return res;
}
}
View Code
2.滑动窗口的平均值（一般看见滑动窗口就应该想起线性的结构）
给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。
实现 MovingAverage 类：
MovingAverage(int size)用窗口大小size初始化对象。double next(int val)成员函数next每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后size个值的移动平均值，即滑动窗口里所有数字的平均值。
题解：就是利用队列的先进先出的特性，队列的大小就是窗口大小，到添加元素让队列大于size就让窗口向后滑动，利用队列让队头出队
package com.chenghaixiang.jianzhi2.day14;
import java.util.ArrayDeque;
import java.util.Queue;
/**
* @author 程海翔
* @school 石家庄铁道大学
*/
public class Office041 {
}
//给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。
//
//实现 MovingAverage 类：
//
// MovingAverage(int size) 用窗口大小 size 初始化对象。
// double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。
class MovingAverage {
Queue<Integer> queue;
int size;
double sum;
/** Initialize your data structure here. */
public MovingAverage(int size) {
queue=new ArrayDeque<>();
this.size=size;
sum=0;
}
//利用队列先进先出的特性
public double next(int val) {
//当当前队列大于size是证明要让窗口向后滑动，队头出列
if(queue.size()==size){
sum-=queue.poll();
}
queue.offer(val);
sum+=val;
return sum/queue.size();
}
}
View Code
标签：总结,窗口,int,MovingAverage,算法,temperatures,滑动,size From： https://www.cnblogs.com/chenghaixiang/p/16606578.html