Java基本数据类型 Synchnorized JS iphone authentication text loam算法测试 permissions uiwebview vue开发文档 vue架构 android经典项目开发实战 网络营销视频 oracle无效的列索引 mysql在线测试 鼠标失去焦点事件 destoon python中的join函数 python的编译器 python如何调用函数 python获取输入 java连接mysql javafinally java正则表达式匹配 java文档 java当前时间 java流程 linuxtail命令 服务器操作系统下载 风火云 网络文件服务器 魔兽地图七个人 凤凰刷机 gg修改器下载 模拟按键 抠图软件免费版 python图片处理 女圣骑 小米手环怎么连接手机 ps怎么做漂亮艺术字
当前位置: 首页 > 学习教程  > 编程语言

滑动窗口问题

2021/1/28 23:38:03 文章标签:

滑动窗口问题 ​ 牛客网 NC 87 滑动窗口的最大值, 题目描述 给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的…

滑动窗口问题

​ 牛客网 NC 87 滑动窗口的最大值

题目描述

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

窗口大于数组长度的时候,返回空。

示例

输入:

[2,3,4,2,6,2,5,1],3

输出:

[4,4,6,6,6,5]

解题思路–双指针

​ 当窗口向右滑动时我们需要考虑两点,一是之前的最大值是否仍然有效(在窗口范围内),即之前的最大值下标是否大于等于窗口的左边界。当之前的最大值下标在窗口范围内时,此时只需判断滑动窗口右侧新增加的数是否大于最大值,做相应更新最大值和最大值下标操作。而最大值下标已经失效时,此时最大值失效,我们就需要重新计算从窗口左侧到右侧的最大值。

​ 我们把滑动窗口的左右边界分别设置为 i 和 j ,初始化时 i = 0,j = 滑动窗口大小 - 1,最大值下标maxInd = -1为了让第一次循环时计算出 i 到 j 区间的最大值。 而上面提到的最大值失效,即最大值下标maxInd = i - 1 < i,此时我们需要重新计算 i 到 j 区间内的最大值。而最大值有效值,只需要判断新加入滑动窗口的数 num[j] 是否大于之前的最大值。

import java.util.*;

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> list = new ArrayList();
        int n = num.length;
        if(n < size || size == 0 || n == 0)
            return list;
        int i = 0, j = size - 1;
        int maxVal = 0, maxInd = -1;
        while(j < n) {
            //最大值下标小于i,需要计算从i到j的最大值
            if(maxInd < i) {
                int k = i + 1;
                maxVal = num[i];
                maxInd = i;
                while(k <= j) {
                    if(maxVal < num[k]) {
                        maxInd = k;
                        maxVal = num[k];
                    }
                    k++;
                }
            //最大值下标maxInd大于等于i(最大值仍然有效)
            //只需要判断新划入到窗口内的num[j]是否大于最大值maxVal
            } else {
                if(maxVal < num[j]) {
                    maxVal = num[j];
                    maxInd = j;
                }
            }
            ++i; ++j;
            list.add(maxVal);
        }
        return list;
    }
}

本文链接: http://www.dtmao.cc/news_show_650255.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?