LeetCode 453

給你一個(gè)長(zhǎng)度為?n?的整數(shù)數(shù)組，每次操作將會(huì)使?n - 1?個(gè)元素增加?1?。返回讓數(shù)組所有元素相等的最小操作次數(shù)。

第一次看到題目的時(shí)候，我最大的疑問(wèn)是怎么保證操作次數(shù)最少，然后想到了讓最小的數(shù)加到和第二小的數(shù)的一樣大，然后讓第二小的數(shù)加到和第三小的數(shù)一樣大，直到相等，記錄總次數(shù)......這是直覺(jué)上的方案，所以我還是不敢相信這樣就是最少的步驟，就像動(dòng)態(tài)規(guī)劃那個(gè)經(jīng)典題目里，讓你用5 7 2 三種面值的錢湊27塊一樣，直覺(jué)上是先用大面值但結(jié)果并不是最少。

但提交了一下居然直接通過(guò)了。

我還寫了注釋來(lái)模擬步驟，后面的3 4 5 8就是前一個(gè)數(shù)字要和后一個(gè)數(shù)字一樣大，需要加的次數(shù)。雖然通過(guò)了，但內(nèi)存和速度慘不忍睹，于是我覺(jué)得一定有更簡(jiǎn)單的方法，然后開(kāi)始看注釋，想找出那四個(gè)數(shù)字和數(shù)組之間有沒(méi)有什么規(guī)律......

結(jié)論是，沒(méi)有。然后我開(kāi)始換思路，我覺(jué)得是排序拖慢了我的速度，就想著怎么能避免排序......沒(méi)想出來(lái)。

然后去看了一眼官方題解，一個(gè)殘酷的事實(shí)擺在我的面前：

只需要計(jì)算每個(gè)數(shù)和最小值的差值，然后把它們相加就行了。

我看了一眼自己的代碼，我做的實(shí)際上就是這件事，只不過(guò)我根本沒(méi)意識(shí)到這些數(shù)字都是和最小值的差值！我把3 4 5 8 這四個(gè)差值都寫出來(lái)了，卻完全沒(méi)發(fā)現(xiàn)它就是差值，只是把它當(dāng)作前一個(gè)數(shù)要和后一個(gè)數(shù)相等需要加的次數(shù)......

可以利用“相對(duì)論”，把所有數(shù)+1視為一個(gè)數(shù)-1，這種類似腦筋急轉(zhuǎn)彎的思路沒(méi)想到很正常。但這四個(gè)值是每個(gè)數(shù)和最小值的差值，這件事應(yīng)該是可以發(fā)現(xiàn)的。

正確答案擺在我的面前，我都沒(méi)發(fā)現(xiàn)這是答案......我現(xiàn)在就和鉆1晉級(jí)賽渡劫局，還差一下就能把對(duì)面水晶a爆，結(jié)果掉線連上以后發(fā)現(xiàn)自家水晶爆了一樣難受。