算法笔试模拟题精解之“最强的团队”

在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：

https://developer.aliyun.com/coding

本文为大家介绍其中的 第37题：最强的团队 的题目解析，具体如下：

题目描述

题目等级：简单

知识点：贪心

查看题目：最强的团队

有一个阵营，里面有n个小队(1<=n<=100)，每个小队都有他们的能力值ai(0<=i

现在有一个紧急情况，需要从这些小队中选出连续的几个小队，组成一个最强的团队。最强的团队的定义为这个团队的所有小队的平均能力值最高。如果有多个最强团队，则选包含小队最多的一个。

现在请你写个程序，输出这个最强的团队包含的小队的个数。

输入小队的数量n，和n个数，分别代表各小队的能力值ai

输出一个数表示这个最强团队包含的小队的个数。

示例1

输入：

6

[1,2,3,3,2,1]

输出：

2

解题方法

根据题意，最强团队即团队中每个小队的能力值都是最高的。即解决这道题需要找出数组中连续最大值的个数，若有多个连续最大值，选择个数最多的。

具体实现时，可以先找出数组中最大的能力值是多少，然后设置一个标记tag。接着遍历数组，比较每个数组元素和最大值，数组元素等于最大的值的时候，将tag标记为1，数组元素不等于最大值时，将tag置为0。

在tag等于1时统计连续最大值的数量，若统计到多个最大值，则记录最大的那个。

时间复杂度：O(n^2)

空间复杂度：O(1)

看完之后是不是有了想法了呢，快来练练手吧>>