剑指offer题解--⑧滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。

解题思路

按照自己的思路来说的话，比较蠢；
假设数组的长度为m,滑动窗口的大小为n,保证m >= n的前提下，可以得出 每一个小窗口的大小为n，滑动次数为(m-n + 1)次，那么我的方法是把每一个子窗口都构造出来，再通过getMax方法，等到最大值，插入到返回的list里面;记得一些特殊校验就好了。

代码演示

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size){
        int length = num.length;
        if(size <= 0){
            return new ArrayList<>();
        }
        if (length == 0){
            return new ArrayList<>();
        }


        if (length < size){
            return new ArrayList<>();
        }
        if (length == size) {
            ArrayList<Integer> r = new ArrayList<>();
            r.add(getMax(num));
            return r;
        }else{
            int time = length - size + 1;
            ArrayList<Integer> result = new ArrayList<>(time);
            int begin = 0;
            int end = size - 1;
            for (int i = 0; i < time; i++) {
                int[] temp = new int[size];
                int index = 0;
                for (int j = begin; j <= end ; j++) {
                    temp[index ++ ] = num[j];
                }
                Integer max = getMax(temp);
                result.add(max);
                begin ++ ;
                end ++;
            }
            return result;
        }
    }
    private Integer getMax(int[] num) {
        int max = Integer.MIN_VALUE;
        for (int i : num) {
            if (i > max){
                max = i;
            }
        }
        return max;
    }
}