专栏首页chenjx85的技术专栏leetcode-643-Maximum Average Subarray I

leetcode-643-Maximum Average Subarray I

题目描述:

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

  1. 1 <= k <= n <= 30,000.
  2. Elements of the given array will be in the range [-10,000, 10,000].

要完成的函数:

double findMaxAverage(vector<int>& nums, int k)

说明:

这道题目十分容易,给定一个vector和数值k,我们可以得到长度为k的多个连续的子vector,要求返回这些子vector中的最大平均值。

我们可以遍历一遍vector就得到了结果,存储和的最大值,最后除以k即可得到。

为了降低花费的时间,我们也不需要每次都计算k个元素的和,减去最前面一个和加上新增加的一个即可,类似于滑动窗口。

代码如下:

    double findMaxAverage(vector<int>& nums, int k) 
    {
        int s1=nums.size();
        int sum=0;
        for(int i=0;i<k;i++)
            sum+=nums[i];
        int i=1,max1=sum;
        while(i+k<=s1)
        {
            sum-=nums[i-1];
            sum+=nums[i+k-1];
            max1=max(max1,sum);
            i++;
        }
        return double(max1)/k;
    }

上述代码实测174ms,beats 81.87% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-46-全排列

    vector<vector<int>> permute(vector<int>& nums) 

    chenjx85
  • leetcode-661-Image Smoother

    chenjx85
  • leetcode-77-组合

    vector<vector<int>> combine(int n, int k) 

    chenjx85
  • LeetCode 473 Matchsticks to Square

    Remember the story of Little Match Girl? By now, you know exactly what matchstic...

    Yano_nankai
  • LeetCode 724:寻找数组的中心索引 Find Pivot Index

    Given an array of integers nums, write a method that returns the "pivot" index o...

    爱写bug
  • Educational Codeforces Round 60 (Rated for Div. 2) A. Best Subsegment(思维)

    版权声明:欢迎转载,若转载,请标明出处,如有错误,请指点,也欢迎大佬们给出优化方法 https://blog.csdn.net/Charles_Zaqd...

    Ch_Zaqdt
  • POJ 1018 Communication System

    Communication System Time Limit: 1000MS Memory Limit: 10000K Total Submi...

    Angel_Kitty
  • Golang语言社区--Go语言基础第六节函数

    大家好,我是Golang语言社区主编彬哥,本篇给大家带来的是关于Go语言中的函数。

    李海彬
  • Android开发:获取当前系统时间和日期的方法

    最近接手了公司Android项目,一直在处理Android项目的App的开发,作为半路起家,总结了一些Android开发的心得和知识点,然后就写下来记录一下,分...

    三掌柜
  • POJ 2594 Treasure Exploration

    Description Have you ever read any book about treasure exploration? Have you ev...

    attack

扫码关注云+社区

领取腾讯云代金券