文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 暴力超時
    • 2.2 二分查找

1. 題目

給定一個包含 n 個整數的數組，找到最大平均值的連續子序列，且長度大于等于 k。并輸出這個最大平均值。

樣例 1: 輸入: [1,12,-5,-6,50,3], k = 4 輸出: 12.75 解釋: 當長度為 5 的時候，最大平均值是 10.8， 當長度為 6 的時候，最大平均值是 9.16667。 所以返回值是 12.75。注釋 : 1 <= k <= n <= 10,000。 數組中的元素范圍是 [-10,000, 10,000]。 答案的計算誤差小于 10-5 。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-average-subarray-ii
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 暴力超時

59 / 74 個通過測試用例

class Solution { public:double findMaxAverage(vector<int>& nums, int k) {int n = nums.size(), i, j, s;double maxAVG = INT_MIN, avg;vector<int> sum = nums;for(i = 1; i < n; ++i)sum[i] = sum[i-1] + nums[i];for(i = 0; i <= n-k; ++i)for(j = i+k-1; j < n; ++j){if(i == 0)s = sum[j];elses = sum[j]-sum[i-1];avg = s/double(j-i+1);if(avg > maxAVG)maxAVG = avg;}return maxAVG;} };

2.2 二分查找

class Solution { public:double findMaxAverage(vector<int>& nums, int k) {double l = -10000, r = 10000, mid, ans;while(r-l > 1e-6){mid = (l+r)/2.0;if(isok(nums, mid, k)){l = mid;ans = mid;}elser = mid;}return ans;}bool isok(vector<int> nums, double avg, int k){ //存在長度至少為k，且均值 >= avg 嗎？double sum = 0, prev = 0, minprev = 0;//前面最小的前綴和0（長度為0時）for(int i = 0; i < k; ++i)sum += nums[i]-avg;//每個數減去平均值，求和 >= 0 存在即okif(sum >= 0) return true;for(int i = k; i < nums.size(); ++i){sum += nums[i]-avg;prev += nums[i-k]-avg;minprev = min(minprev, prev);//前面最小的和（減去avg后的）if(sum-minprev >= 0)//存在區間，使得減去avg后sum>=0return true;}return false;} };

208 ms 90.3 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 644. 最大平均子段和 II（二分查找）*的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。