滑动窗口的最大值

1、模拟法---带加速(时间换空间)

1.解题思路

模拟滑动过程
利用上一个窗口的preMaxIndex（最大值下标）来加速下一个滑动窗口最大值的查找
- preMaxIndex在新的滑动窗口[start,end]之间，则判断上一个滑动窗口最大值num[preMaxIndex]与新增的一个值num[end]比较大小，返回index
  - ```
  if(num[preMaxIndex] <= num[end])
      return end;
  else 
      return preMaxIndex;
```
- preMaxIndex不在新的滑动窗口[start,end]之间，则利用findIndexOfMax函数，寻找：数组[start,end]范围内的最大值的下标(靠右)

2.代码

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer>  maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> maxA = new ArrayList<>();
        if(num == null || size < 1 || num.length < size )  // 关键是此处的条件
            return maxA; 
        int len = num.length;
        int start = 0,end = start + size - 1;
        //preMaxIndex上一个滑动窗口最大值的下标
        int preMaxIndex = findIndexOfMax(num,start,end);  
        maxA.add(num[preMaxIndex]);
        for(int start=1,end = start + size - 1;start <= (len - size);start++,end++){ 
             //找每个滑动窗口的max值，i为每个滑动窗口起始index值
             int newMaxIndex = maxNumIndexOfWindow(num,preMaxIndex,start,end);
             maxA.add(num[newMaxIndex]);
             preMaxIndex = newMaxIndex;
        }
        return maxA;

    }
    int maxNumIndexOfWindow(int[] num,int preMaxIndex,int start,int end){
        if(start <= preMaxIndex && preMaxIndex <= end){
            // 如果preMaxIndex在新的滑动窗口[start,end]之间
            // 则判断上一个最大值与新增的一个值num[end]比较大小，返回index
            return (num[preMaxIndex] <= num[end])? end : preMaxIndex;
        }else{
            // 如preMaxIndex不在新的滑动窗口[start,end]之间
            // 直接找新滑动窗口的max值的下标
            return findIndexOfMax(num,start,end);
        }
    }
    int findIndexOfMax(int[] num,int start,int end){
        // 返回 数组[start,end]范围内的最大值的下标(靠右)
        int max = num[start];
        int index = start;
        for(int i=start;i<=end;i++){
            if(num[i] >= max){
                max = num[i];
                index = i;
            }
        }
        return index;
    }
}

3.复杂度

时间复杂度
- 最坏情况：O(size * (N-size) )
  - N - size：为滑动窗口的个数
  - 每次查找，preMaxIndex都不在新滑动窗口的范围内
- 最好情况O(size + N-size) = O(N)
  - 每次查找，preMaxIndex都在新滑动窗口的范围内
- 平均时间复杂度：O(???)
空间复杂度：O(1)

4.遇到的坑

这几个条件都返回空数组[]：
- num == null
- || num.length == 0
- || size == 0
- || num.length < size

2、优先队列（空间换时间）

1.解题思路

维护一个优先队列----滑动窗口
1. 如何保证栈顶是当前滑动窗口的最大值，而不是上一个滑动窗口留下的

2.代码

import java.util.ArrayList;
import java.util.PriorityQueue;
public class Solution {
    public ArrayList<Integer>  maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> ret = new ArrayList<>();
        if (size > num.length || size < 1)
            return ret;
        PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);  /* 大顶堆 */
        for (int i = 0; i < size; i++)
            heap.add(num[i]); //第一个滑动窗口
        ret.add(heap.peek());
        for (int i = 0, j = i + size; j < num.length; i++, j++) {            /* 维护一个大小为 size 的大顶堆 */
            // i为上一个窗口的startIndex  j为本次窗口的endIndex
            // 总环次数为窗口数
            // 删除、进入模拟滑动过程
            heap.remove(num[i]);  // 删除操作 O(log(size))
            heap.add(num[j]);     // 入堆操纵 O(log(size))
            ret.add(heap.peek()); // 取栈顶，为最大值
        }
        return ret;
    }
}

3.复杂度

时间复杂度：O( size + (N - size) * size )
- size为构建堆的复杂度
- (N - size)为滑动窗口的个数
- size为删除元素的复杂度
空间复杂度：O(size)

4.遇到的坑

不知道优先队列还有删除操作