一、209. 长度最小的子数组
难度中等
题目描述
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3]
是该条件下的长度最小的连续子数组。
分析:采用滑动窗口,i,j分别表示左边界和右边界,sto用来存储i-j之间数值的和,res用来存储j-i。
最外层循环判定循环结束,即左侧边界到达倒数第二个位置(因为默认j一定在i的右边)
当sto<s&&j<len的时候右边界右移,否则(j到达最右边,或者sto>=s)移动左边界
res则不停的判断是否有更小的距离,前提条件都是:
if(sto>=s){
res=Math.min(res,j-i);
}
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int len=nums.length;
if(len==0)return 0;
int i=0;
int j=1;
int res=len+1;
int sto=nums[0];//用于存储当前添加值
while(i<len-1){
if(sto<s&&j<len){
sto+=nums[j];
j++;
}
else {
if(sto>=s){
res=Math.min(res,j-i);
}
i++;
sto-=nums[i-1];
}
}
if(res==len+1)res=0;
return res;
}
}
二、剑指offer(63) 滑动窗口的最大值
1.题目描述
给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。
例如,如果输入数组{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.分析
我的解法:
1.设立两个用于比较的值,maxValue和maxIndex,指示当前用于比较的最大值以及他的下标
2.先对第一个滑动窗口进行比对,得出maxValue=4,maxIndex=2,并添加到ArrayList中
{[2,3,4],2,6,2,5,1}
3.然后从index=3的位置逐步往后比较maxValue的值,遇到更大的就替换maxValue和maxIndex为新的值
{2,3,[4,2,6],2,5,1},如第三个滑动窗口,maxValue替换为6,maxIndex替换为4
依此类推......
4.这个过程可能会遇到,超出当前maxValue的比对范围的情况,
如:{2,3,4,2,6,[2,5,1]}
maxValue=6,maxIndex=4,但是现在已经到"1"所在的位置,超出了窗口范围
因此采用一层循环,从"2"~"5"之间,重新设定maxVlue和maxIndex
5.从头遍历到尾,每次循环将maxValue添加到ArrayList中。(要注意边界条件 size<=0||len<=0||size>len)
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> memo = new ArrayList<>();
int len = num.length;
//牛客网几乎所有不符合条件的都是返回空,务必要注意
if(size<=0||len<=0||size>len)return memo;
int maxValue = Integer.MIN_VALUE;
int maxIndex = -1;
for(int i=0;i<size;i++){
if(i<len&&num[i]>maxValue){
maxValue = num[i];
maxIndex = i;
}
}
//可以判断,如果size<=0,保证memo为null
if(maxIndex!=-1){
memo.add(maxValue);
}
for(int i=size;i<len;i++){
//如果超出前面最大值的比较范围,则需要重新设定
//以下循环,判断到i之前的一个最大值
if(i-maxIndex>=size){
int j = i-size+1;
maxValue = num[j];
while(j<i){
if(num[j]>maxValue){
maxValue = num[j];
maxIndex = j ;
}
j++;
}
}
if(num[i]>maxValue){
maxValue = num[i];
maxIndex = i;
}
memo.add(maxValue);
}
return memo;
}
}
其他解法:
待补充!
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)