https://leetcode-cn.com/problems/magnetic-force-between-two-balls/

pic1.png

這道題目的解法對我很有啟發(fā)，所以寫下這篇博客，加深理解。

看到這道題目，基于以往的做題經(jīng)驗(yàn)，第一時(shí)間的想法是搜索，于是思路如下：

方法一

1. 先將 m個(gè)球按照 position位置緊挨著排，也就是說，m個(gè)球的位置分別是
   position[0], position[1], position[2]...position[m-1]
2. 除了第一個(gè)球，逐個(gè)后移調(diào)整每個(gè)球的位置，每次調(diào)整去統(tǒng)計(jì) |position[i] - position[j]| 的最小值
3. 重復(fù)步驟2 直到 m個(gè)球的位置分別是
   position[len(position)-m], position[len(position)-(m-1)], position[len(position)-(m-2)]...position[position[len(position)-1]]
4. 步驟2結(jié)果的最大值則為題解

顯然這種方法有點(diǎn)愚蠢，于是想到了優(yōu)化

方法二

我想到每次調(diào)整可以從 |position[i] - position[j]| 的最小值所在的兩個(gè)球去調(diào)整，不必移動(dòng)所有的球，如果同時(shí)有幾個(gè)球之間的距離為最小值，從左往右依次移動(dòng)。

如果最后一個(gè)球超出了 position的范圍，則說明本次移動(dòng)是無效的，移動(dòng)之前的距離最小值則為題解

這種方法看似可行，但是時(shí)間復(fù)雜度還是太高，統(tǒng)計(jì)最小值和移動(dòng)元素的時(shí)間成本太高。

方法三

如果仔細(xì)思考方法二我們會(huì)發(fā)現(xiàn)。

我們實(shí)質(zhì)上是在一步步增加最小磁力的大小，而最小磁力的最大值一定會(huì)大于0，小于 position[len(position)-1] / (m - 1)。

為了減小時(shí)間復(fù)雜度，我們可以 “步子邁大一點(diǎn)”，不必逐次增加，我們可以采用二分法。

我們將對最小磁力的范圍進(jìn)行二分，最小值為 min = 0，最大值為 max = position[len(position)-1] / (m - 1)

每次二分之后去檢查當(dāng)前所獲取的最小磁力的值是否滿足題目的要求，如果滿足，則我們繼續(xù)按照二分法增加最小磁力的大小，如果不滿足，則我們?nèi)p小最小磁力的大小

代碼如下：

func maxDistance(position []int, m int) int {
    sort.Ints(position)
    var (
        min int = 0
        max int = (position[len(position)-1] / (m - 1))
        mid int
        ans int
    )
    for min <= max {
        mid = (max + min) / 2
        if check(position, m, mid) {
            ans = mid
            min = mid + 1
        } else {
            max = mid - 1
        }
    }
    return ans
}

func check(position []int, m int, k int) bool {
    i := 1
    lastPO := position[0]
    m--
    for i < len(position) {
        if position[i]-lastPO >= k {
            m--
            lastPO = position[i]
        }
        i++
    }
    return m <= 0
}

對比方法二的一步一步走，方法三分隔解區(qū)間的方法似乎來得更有效，這就類似于排序數(shù)組中的查找

這里我們需要注意的是，方法二，我們是根據(jù) position的值去調(diào)整球的位置。而方法三，我們是根據(jù)二分的結(jié)果，去判斷當(dāng)前間隔是否合法。

啟發(fā)

這道題給我的啟發(fā)就是，合理的利用二分法。在做題之前我思考過搜索，時(shí)間復(fù)雜度太高。思考過dp，怎么也找不到遞推關(guān)系。完全沒有往二分的方向去思考，直到看了題解才恍然大悟。

稍微總結(jié)了一下適用二分法題目的特點(diǎn)：

1. 解區(qū)間是有限的，有最大值和最小值
2. 存在某一種處理方法（這里是 check函數(shù)）能將解區(qū)間分為兩部分，而每一部分又能使用同樣的方法分隔
3. 解是單調(diào)的，此題中，假設(shè)間隔 n無法滿足要求，則間隔 n+1，n+2...均無法滿足要求，而如果 n滿足要求，則間隔 n-1，n-2均是滿足要求的（此題中，雖然可能會(huì)出現(xiàn)某些間隔是無效的，譬如 position為 [1,4,7] m=3，此時(shí)解為 3，解 1和2并不存在。但 1 和 2 只是我們用來尋找 3 的一個(gè)跳板，他們并不是最終解）

博主水平不足，若有不足，請斧正