剑指offer-64-滑动窗口的最大值

思路

• 3指针，定义个max指针，p指针，指针q=p-3+1，显然指针p,q可以合并。
  p: 0->len(num)
  max有两种情况
  • 如果指针p>max（是值大于），直接更新max=p
  • 如果指针q>max，那么遍历q到p,更新max为区间最大值
    其实类似牛客题解中的单调队列吧。相比建队列，指针法复杂度为o(1),时间复杂度相同

代码

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {   ArrayList<Integer> arr=new ArrayList<>();
        if(size==0||size>num.length){return arr;}
        int max=0,p=0,q=p-size+1;
        while(p<num.length){
            if(num[p]>=num[max]){
                max=p;
            }
            if(q>max){
                max=q;
                for(int i=q;i<=p;i++){
                    max=num[i]>num[max]?i:max;
                }
            }
            // q>=0开始有滑动窗口了
            if(q>=0){
                arr.add(num[max]);
            }
            p++;
            q++;
        }
     return arr;
    }
}