[LeetCode644]最大平均サブアレイII
Maximum Average Subarray Ii
正の数と負の数の配列が与えられた場合、maximum average subarrayを見つけます。どの長さが指定された長さk以上である必要があります。
例
例1：
Input: [1,12,-5,-6,50,3] 3 Output: 15.667 Explanation: (-6 + 50 + 3) / 3 = 15.667 例2：
Input: [5] 1 Output: 5.000 通知
配列のサイズが以上であることが保証されています に 。
分析
このトピックは良いトピックです。元の二分法では、特定の配列のバイナリスコアを作成できるだけでなく、目的の結果をバイナリ検索することもできます。
O（n ^ 2）の解決策をすぐに考えることができます。これは、可能なすべての間隔をトラバースしてから最大の結果を記録することですが、これはタイムアウトになります。
では、より複雑なソリューションはありますか？
まず、配列の間隔を平均したい場合、この平均には範囲がありますか？もちろん、配列内の任意の間隔の平均は、配列の最大値maxNumと最小値minNumの間にある必要があります。では、最終的に必要となる一連の結果がわかったので、この結果を段階的に見つけるにはどうすればよいでしょうか。
このとき、二分探索法を使用できます。最初に[minNum、maxNum]で検索し、middle =（maxNum + minNum）/ 2とします。次に、k以上の連続長があるかどうかを判断します。間隔の平均値がmiddleに等しい場合は、検索を続行します（middle、maxNum）。そうでない場合は、検索（minNum、middle）します。最後の検索間隔を知るmaxNum-minNum さて、この時点で、最後の問題を解決する必要があります。つまり、配列内にk以上の連続長があるかどうか、間隔の平均値が中央以上であるかどうかをどのように判断するかです。 最初に問題を単純化し、配列内のすべての値を中央から減算してから、質問を配列内にk以上の連続長があるかどうかに変換できます。 leftMinSum [i]を使用して、区間[0、n]（nの最小合計を表します。<= i) in the interval [0, i], then if there is a [m, i+k] interval m <= i +1, the interval And greater than or equal to 0. Then there must be Sum[i+k] - leftMinSum[i]>0.それ以外の場合、[0、i]の最小間隔合計が条件を満たさない場合、mが存在してはならないため、[m、i + k]の間隔の合計はゼロより大きくなります。したがって、前後から配列をトラバースし、Sum [i + k] --leftMinSum [i]> 0となるような条件があるかどうかを計算します。 コード 運用効率 あなたの提出物は15.00％の提出物を上回ります！class Solution { public: /** * @param nums: an array with positive and negative numbers * @param k: an integer * @return: the maximum average */ double maxAverage(vector &nums, int k) { // write your code here int len = nums.size() double maxNum = nums[0] double minNum = nums[0] for (int i = 1 i <= len i ++) { maxNum = max(maxNum, nums[i]) minNum = min(minNum, nums[i]) } while (maxNum - minNum> 1e-5) { double middle = (maxNum + minNum)/2 if (canFind(nums, k, middle)) { minNum = middle } else { maxNum = middle } } return maxNum } bool canFind(vector& nums, int k, double average) { int len = nums.size() vector dec(len, 0) for (int i = 0 i