滑动窗口的最大值

题目描述

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

解题思路

题目情况共分为以下几种：

• num 为空；

• size 是 0；

• size 大于 num 长度。

以上四种情况均返回无值 ArrayList。

• 第一组数据：

  • 直接计算组内的最大值，返回最大值的 index；

• 非第一组：

  • 如果新数据 >=上一最大值，更新 index 为新数据的 index；

  • 如果新数据 < 上一最大值，且 index 不在本组范围内，直接计算本组的最大值。

代码

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (num == null || num.length == 0 || size == 0 || size > num.length)
            return ret;
        int index = maxIndex(num, 0, size);
        ret.add(num[index]);
        for (int i = size; i < num.length; i++) {
            if (num[i] >= num[index])
                index = i;
            else if (index < i-size+1)
                index = maxIndex(num, i-size+1, i+1);
            ret.add(num[index]);
        }
        return ret;
    }
    
    private int maxIndex(int[] num, int start, int end) {
        int index = start;
        for (int i = start; i < end; i++)
            index = num[i] > num[index] ? i : index;
        return index;
    }
}