单调栈

单调栈，顾名思义就是栈内元素单调按照递增(递减)顺序排列的栈。

单调递增栈：

①在一个队列中针对每一个元素从它右边寻找第一个比它小的元素

②在一个队列中针对每一个元素从它左边寻找第一个比它小的元素

单调递减栈：

①在一个队列中针对每一个元素从它右边寻找第一个比它大的元素

②在一个队列中针对每一个元素从它左边寻找第一个比它大的元素

Stack.peek()

peek()函数返回栈顶的元素，但不弹出该栈顶元素。

Stack.pop()

pop()函数返回栈顶的元素，并且将该栈顶元素出栈。

思想：

当前栈顶的意思是已经存在里面的了

i是将要存进去的

两个相比 然后如果i的数值大直接返回 相减的数值 否则 直接压入栈内

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n=temperatures.length;
        Stack<Integer> stack=new Stack<>();
        int[] ret=new int[n];
        for(int i=0;i<n;i++){
            while(!stack.empty()&& temperatures[stack.peek()]<temperatures[i]){
                int index=stack.pop();
                ret[index]=i-index;
            }stack.push(i);
        }
        return ret;
    }
}

滑动窗口

在 Queue 中 poll()和 remove()有什么区别

• 相同点：都是返回第一个元素，并在队列中删除返回的对象。
• 不同点：如果没有元素 poll()会返回 null，而 remove()会直接抛出 NoSuchElementException 异常。

offer，add区别

一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。

这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。 

peek，element区别：

element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null

class MovingAverage {
    private int length;
    private Queue<Integer> queue;
    private double sum = 0;
 
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        length=size;
        queue=new LinkedList<Integer>();
        sum=0;
    }
    
    public double next(int val) {
        if(queue.size()==length){
            sum-=queue.remove();
        }
        queue.add(val);
        sum+=val;
        return sum/queue.size();
    }
}

重点是在当遍历发现原有的数组和滑动窗口的量相同时

先remove或者poll队列的首段然后再加入尾端

然后再进行相除

双端队列

ArrayDeque是java中对双端队列的线性实现

一.特性

1. 无容量大小限制，容量按需增长；
2. 非线程安全队列，无同步策略，不支持多线程安全访问；
3. 当用作栈时，性能优于Stack，当用于队列时，性能优于LinkedList
4. 两端都可以操作
5. 具有fail-fast特征
6. 不能存储null
7. 支持双向迭代器遍历

class RecentCounter {
    Queue<Integer> queue;
    public RecentCounter() {
        queue=new ArrayDeque<Integer>();
 
    }
    
    public int ping(int t) {
        queue.offer(t);
        while(queue.peek()<t-3000){
            queue.poll();
 
        }
        return queue.size();
    }
}

队列
我们可以用一个队列维护发生请求的时间，当在时间 tt 收到请求时，将时间 tt 入队。

由于每次收到的请求的时间都比之前的大，因此从队首到队尾的时间值是单调递增的。当在时间 tt 收到请求时，为了求出 [t-3000,t][t−3000,t] 内发生的请求数，我们可以不断从队首弹出早于 t-3000t−3000 的时间。循环结束后队列的长度就是 [t-3000,t][t−3000,t] 内发生的请求数。