剑指offer：滑动窗口的最大值

忘是亡心i 2021-06-24 16:10 408阅读 0赞

**试题：**  
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为\{4,4,6,6,6,5\}； 针对数组\{2,3,4,2,6,2,5,1\}的滑动窗口有以下6个： \{\[2,3,4\],2,6,2,5,1\}， \{2,\[3,4,2\],6,2,5,1\}， \{2,3,\[4,2,6\],2,5,1\}， \{2,3,4,\[2,6,2\],5,1\}， \{2,3,4,2,\[6,2,5\],1\}， \{2,3,4,2,6,\[2,5,1\]\}。

**代码：**  
1、当访问下一个窗口时，其实只是在前一个窗口上新加一个数，并除去一个数。所以有前面窗口部分求最大值信息可以继续使用。  
2、使用队列，当新加一个数比队列尾部数值都大时，可以除去这些较小值，另外还要除去不在窗口内的值。

技巧：通过队列了保留最大值，以及最大值后面的次大值、次大值后面的次大值。使用数组下标加入队列，通过小标取值，避免了额外记录位置。

import java.util.*;
    public class Solution {
        public ArrayList<Integer> maxInWindows(int [] num, int size)
        {
            ArrayDeque<Integer> que = new ArrayDeque<>(); 
            ArrayList<Integer> res = new ArrayList<>();
            
            for(int i=0; i<num.length; i++){
                while(que.size()>=1 && num[i]>=num[que.peekLast()]){
                    que.pollLast();
                }
                while(que.size()>=1 && i-que.peekFirst()+1>size){
                    que.pollFirst();
                }
                
                que.offerLast(i);
                if(size>=1 && i+1>=size){
                    res.add(num[que.peekFirst()]);
                }
            }
            return res;
        }
    }