主題
題目連結：
題目意譯：
你被給定三個正整數：n 、 index 和 maxSum。你想要一個陣列 nums（索引值從 0 開始）其滿足以下條件：
nums.length == n
nums[i] 為一正整數，其中 0 ≦ i < n。
abs(nums[i] - nums[i+1]) ≦ 1 其中 0 ≦ i < n-1。
nums 中所有元素總和不超過 maxSum。
nums[index] 盡可能地大。
回傳建構出來的陣列中的 nums[index]。
注意到如果 x ≧ 0，abs(x) 等於 x；反之，則等於 -x。
限制：
1 ≦ n ≦ maxSum ≦ 10 ^ 9
0 ≦ index < n
範例測資：
範例 1：
輸入： n = 4, index = 2, maxSum = 6
輸出： 2
解釋： nums = [1,2,2,1] 是滿足所有條件的一個陣列。
沒有陣列滿足所有條件且有著 nums[2] == 3，所以 2 為最大可能的 nums[2] 之值。
範例 2：
輸入： n = 6, index = 1, maxSum = 10
輸出： 3
解題思維：
對答案本身進行二分搜尋法（Binary Search）即可，如這題。
假設我們猜 nums[index] 之值為 M。
此時為了讓總和盡可能的小，從 nums[index] 往左開始 nums[index - 1] 、 nums[index - 2] 、…… 之值依序應為 M - 1 、 M - 2 、……。同樣地，nums[index] 開始往右之值也依序應為 M - 1 、 M - 2 、……。
因為兩側的數字都非常地有規律（等差級數），所以用公式便可以求出總和。
不過因為題目有規定所有 nums[i] > 0。
因此當 index 左側的數字數量（左側剛好就是 index 個數字） > M 時，索引值 0 ～ index - M 的數字應保持在 1，因此 index 左側總和為
M × (M - 1) ÷ 2 + (index - M + 1)
否則一般情況下，總和應為
(2M - index - 1) × index ÷ 2
同樣地，當右側數字數量（有 n - index - 1 個） > M 時，總和應為
M * (M - 1) ÷ 2 + (n - index - M)
反之，總和為
(2M - (n - index)) × (n - index - 1) ÷ 2
求完總和（令其值為 S）後，如果 S > maxSum，則代表我們一開始猜得太大了，應該要猜小一點的 M 值才行；反之，我們可以試著猜更大的 M 值。
最後便可以收斂在一個滿足條件且又盡可能大的 nums[index] 之值。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
