本文共 1544 字，大约阅读时间需要 5 分钟。

前言

本题来自剑指 Offer 59 - I

题目描述

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

解题思路

我们可以通过标准的递归方式实现，题目可以先拆解为，求整个数组中的最大值。

public class GetArrayMax {
       public static void main(String[] args) {
           int[] arr = {
   1, 5, 2, 7, 0, 2, 14, 8};        System.out.println(getMax(arr, 0, arr.length - 1));    }        private static int getMax(int[] arr, int l, int r) {
           if (l == r) {
               return arr[l];        }        int mid = (l + r) / 2;        int lMax = getMax(arr, l, mid);        int rMax = getMax(arr, mid + 1, r);        return Math.max(lMax, rMax);    }}

之后我们在这个基础上，改成求每个滑动窗口上的最大值。

import java.util.Arrays;public class Code_59_1 {
       public static void main(String[] args) {
           Code_59_1 c = new Code_59_1();        int[] arr = {
   1, 5, 2, 7, 0, 2, 14, 8};        int k = 2;//窗口值        int[] maxArr = c.maxSlidingWindow(arr, k);        System.out.println(Arrays.toString(maxArr));    }    public int[] maxSlidingWindow(int[] nums, int k) {
           if (nums.length == 0) {
               return new int[0];        }        int length = nums.length - k + 1;        int[] maxArr = new int[length];        for (int i = 0; i < length; i++) {
               maxArr[i] = getMax(nums, i, k - 1 + i);        }        return maxArr;    }    private static int getMax(int[] arr, int l, int r) {
           if (l == r) {
               return arr[l];        }        int mid = (l + r) / 2;        int lMax = getMax(arr, l, mid);        int rMax = getMax(arr, mid + 1, r);        return Math.max(lMax, rMax);    }}

转载地址：http://jqlrb.baihongyu.com/