【leetcode】滑动窗口最大值

1.题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

注：k小于len(nums)

输入格式:

整数数组nums，以及滑动窗口大小k

第一行为nums，以空格分隔

第二行为k

输出格式:

一行整数，包含每个窗口中的最大值，以空格分隔

输入样例:

在这里给出一组输入。例如：

1 3 -1 -3 5 3 6 7
3

输出样例:

在这里给出相应的输出。例如：

3 3 5 5 6 7

2.解题思路

 步骤

已知num[0], num[1] ....num[k-1] 区间最大值为res，向右移动一次后，只需要比较num[0] 和res的大小

a）如果num[0]< res, 说明最大值在max(num[1],num[2]....num[k-1]) == res， 右移后，只需要判断新元素和res的最大值即可

b)如果num[0]= res, 不确定右移后最大值为哪个，则逐个判断num[1~ k]

3.代码

import java.util.Scanner;

public class Main {

        public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] numsArr = in.nextLine().split(" ");
        int n = numsArr.length;
        int[] nums = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(numsArr[i]);
        }
        int k = in.nextInt();
         
        int res = findMax(nums, 0, k);
        System.out.print(res);
        for (int i = 1; i <= n - k; i++) {
            res = findKRes(nums, i, k, res);
            System.out.print(" "+ res);
        }
       System.out.println();
    }
    

    public static int findMax(int[] nums, int from, int end) {
        int res = nums[from];
        for (int i = from; i < end; i++) {
            res = Math.max(res, nums[i]);
        }
        return res;
    }

    public static int findKRes(int[] nums, int from, int dis, int res) {
        if (from > 0 && nums[from - 1] < res) {
            return Math.max(res, nums[from + dis-1]);
        } else {
            return findMax(nums, from, from + dis);
        }
    }
}