import java.util.ArrayList; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size) { //结果集 ArrayList<Integer> res = new ArrayList<>(); if(num.length < size || size <= 0) return res; int left = 0; int right = size - 1; while(right < num.length){ //先将窗口最左边的元素 给到max int max = num[left]; //遍历窗口的每一个元素,找到最大值 for(int i = left;i <= right; i++){ if(max < num[i]){ max = num[i]; } } //将当前窗口的最大值加入结果集 res.add(max); //整体往前滑 left++; right++; } return res; } }
这样的话每次都要在窗口中找最大值,时间复杂度较高,剑指大神 Krahets 给出了O(1)时间的效率,截图如下
https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/mian-shi-ti-59-i-hua-dong-chuang-kou-de-zui-da-1-6/