算法筆試模拟題精解之“最強的團隊”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

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)

看完之後是不是有了想法了呢，快來練練手吧>>