JZ64 滑动窗口的最大值

JZ64 滑动窗口的最大值

题目：
例如，如果输入数组{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]}。

思路2：标记每个窗口的最大值。
移动窗口时，如果最大值还在窗口内，就跟新加入的值比较，然后再次标记最大值的位置
如果最大值不在窗口内，循环窗口找出最大值

思路2最优时候：每次窗口滑动都遇见最大值，即最大值不会过期，一遍就能找出。O(N)
最差时候，每次都会过期（最大值都是窗口最左边的那个数），每次都要循环遍历（退化成暴力解的情况）。O(K*N), k为窗口大小

//因为和暴力代码写在一块了，所以只有关键部分的代码
//标记每个窗口的最大值。
        //移动窗口时，如果最大值还在窗口内，就跟新加入的值比较，然后再次标记最大值的位置
        //如果最大值不在窗口内，循环窗口找出最大值
        if(size > num.length || size == 0)    return new ArrayList();
        ArrayList<Integer> list = new ArrayList<Integer>();
        int left = 0;
        int right = left + size - 1;
        //找出第一个窗口的最大值
        int max = num[left];
        int index = left;    //最大值的位置
        for(int i=left; i<=right && i<num.length; i++){
            if(num[i] > max){
                max = num[i];
                index = i;
            }
        }
        //先把第一个窗口处理完毕
        list.add(max);
        left++;
        right++;
        while(right <= num.length-1){
            //判断最大值是否还在窗口内
            if(index>=left && index <= right){
                //比较窗口内的新值和最大值的大小
                if(num[right] >= max){
                    //等于时候也要更新最大值位置
                    max = num[right];
                    index = right;
                }

            }else{
                //重新查找窗口内的最大值
                //记得初始化这个窗口的最大值，不然比较的就是以前的值
                max = num[left];
                for(int i=left; i<=right && i<num.length; i++){
                    if(num[i] > max){
                        max = num[i];
                        index = i;
                    }
                }
            }
            list.add(max);
            left++;
            right++;
        }
        return list;

思路1：暴力
遍历数组，然后每个窗口找出最大值即可（面试估计不行）

暴力代码如下

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        //暴力解应该能行
        //1. 暴力
        if(size > num.length || size == 0)    return new ArrayList();
        ArrayList<Integer> list = new ArrayList<Integer>();
        int left = 0;
        int right = left + size - 1;
        while(right <= num.length-1){
            int max = num[left];
            for(int i=left; i<=right; i++){
                if(num[i] > max){
                    max = num[i];
                }
            }
            list.add(max);
            left++;
            right++;
        }
        return list;
    }
}