运行时间：13ms
超过77.89% 用Java提交的代码
占用内存：9656KB
超过14.87%用Java提交的代码

编写一个单调队列

这个队列要有如下功能：

1. 具有MAX函数， 获取当前队列最大值

2. 获取o(1)

   public class SingleQueue {
    LinkedList<Integer> q = new LinkedList<>();
    public void push(int n) {
        // 将小于 n 的元素全部删除
        while (!q.isEmpty() && q.getLast() < n) {
            q.pollLast();
        }
        // 然后将 n 加入尾部
        q.addLast(n);
    }
   
    public int max() {
        return q.getFirst();
    }
   
    public void pop(int n) {
        if (n == q.getFirst()) {
            q.pollFirst();
        }
    }
   }

进行代码编写

import java.util.*;
public class Solution {

    public ArrayList<Integer> maxInWindows(int [] nums, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        if(nums.length == 0){return result;}
        SingleQueue window = new SingleQueue();

        for (int i = 0; i < nums.length && k > 0 ; i++) {
            //少进一个人
            if (i < k - 1) {
                window.push(nums[i]);
            } else {
                //进入
                window.push(nums[i]);
                //找到最大的
                result.add(window.max());
                //出去
                window.pop(nums[i - k + 1]);
            }
        }
        return result;
    }
}