classSolution{public:doublefindMaxAverage(vector<int>&nums,intk){constexprdoublekErr=1e-5;doublel=*min_element(begin(nums),end(nums));doubler=*max_element(begin(nums),end(nums));while(r-l>kErr){constdoublem=(l+r)/2;if(check(nums,k,m))l=m;elser=m;}returnl;}private:// True if there's a subarray with length >= k and average sum >= mboolcheck(constvector<int>&nums,intk,doublem){doublesum=0;doubleprevSum=0;doubleminPrevSum=0;for(inti=0;i<nums.size();++i){// Trick: -m for each num so that we can check if the sum of the// Subarray >= 0sum+=nums[i]-m;if(i>=k){prevSum+=nums[i-k]-m;minPrevSum=min(minPrevSum,prevSum);}// If sum - minPrevSum >= 0,// We know there's a subarray with length >= k and average sum >= mif(i+1>=k&&sum>=minPrevSum)returntrue;}returnfalse;};};
classSolution{publicdoublefindMaxAverage(int[]nums,intk){finaldoublekErr=1e-5;doublel=(double)Arrays.stream(nums).min().getAsInt();doubler=(double)Arrays.stream(nums).max().getAsInt();while(r-l>kErr){finaldoublem=(l+r)/2;if(check(nums,k,m))l=m;elser=m;}returnl;}// True if there's a subarray with length >= k and average sum >= mprivatebooleancheck(int[]nums,intk,doublem){doublesum=0;doubleprevSum=0;doubleminPrevSum=0;for(inti=0;i<nums.length;++i){// Trick: -m for each num so that we can check if the sum of the// Subarray >= 0sum+=nums[i]-m;if(i>=k){prevSum+=nums[i-k]-m;minPrevSum=Math.min(minPrevSum,prevSum);}// If sum - minPrevSum >= 0,// We know there's a subarray with length >= k and average sum >= mif(i+1>=k&&sum>=minPrevSum)returntrue;}returnfalse;}}
classSolution:deffindMaxAverage(self,nums:List[int],k:int)->float:kErr=1e-5l=min(nums)r=max(nums)# True if there's a subarray with length >= k and average sum >= mdefcheck(m:float)->bool:summ=0prevSum=0minPrevSum=0fori,numinenumerate(nums):# Trick: -m for each num so that we can check if the sum of the# Subarray >= 0summ+=num-mifi>=k:prevSum+=nums[i-k]-mminPrevSum=min(minPrevSum,prevSum)# If sum - minPrevSum >= 0,# We know there's a subarray with length >= k and average sum >= mifi+1>=kandsumm>=minPrevSum:returnTruereturnFalsewhiler-l>kErr:m=(l+r)/2ifcheck(m):l=melse:r=mreturnl