前言 瀑布流佈局是前端領域中一個很常見的需求，由於圖片的高度是不一致的，所以在多列佈局中預設佈局下很難獲得滿意的排列。 我們的需求是，圖片高度不規律的情況下，在兩列佈局中，讓左右兩側的圖片總高度儘可能的接近，這樣的佈局會非常的美觀。 註意，本文的目的僅僅是討論演算法在前端中能如何運用，而不是說瀑布流的 ...
瀑布流佈局是前端領域中一個很常見的需求，由於圖片的高度是不一致的，所以在多列佈局中預設佈局下很難獲得滿意的排列。
我們的需求是，圖片高度不規律的情況下，在兩列佈局中，讓左右兩側的圖片總高度儘可能的接近，這樣的佈局會非常的美觀。
註意，本文的目的僅僅是討論演算法在前端中能如何運用，而不是說瀑布流的最佳解法是動態規劃，可以僅僅當做學習拓展來看。
分析
從預覽圖中可以看出，雖然圖片的高度是不定的，但是到了這個佈局的最底部，左右兩張圖片是正好對齊的，這就是一個比較美觀的佈局了。
那麼怎麼實現這個需求呢？從頭開始拆解，現在我們能拿到一組圖片數組 [img1, img2, img3]，我們可以通過一些方法得到它對應的高度 [1000, 2000, 3000]，那麼現在我們的目標就是能夠計算出左右兩列 left: [1000, 2000] 和 right: [3000] 這樣就可以把一個左右等高的佈局給渲染出來了。
準備工作
首先準備好小姐姐數組 SISTERS：
let SISTERS = [ 'https://pic3.zhimg.com/v2-89735fee10045d51693f1f74369aaa46_r.jpg', 'https://pic1.zhimg.com/v2-ca51a8ce18f507b2502c4d495a217fa0_r.jpg', 'https://pic1.zhimg.com/v2-c90799771ed8469608f326698113e34c_r.jpg', 'https://pic1.zhimg.com/v2-8d3dd83f3a419964687a028de653f8d8_r.jpg', ... more 50 items ] 複製代碼
準備好一個工具方法 loadImages，這個方法的目的就是把所有圖片預載入以後獲取對應的高度，放到一個數組裡返回。並且要對外通知所有圖片處理完成的時機，有點類似於 Promise.all 的思路。
這個方法里，我們把圖片按照 寬高比 和屏幕寬度的一半進行相乘，得到縮放後適配屏寬的圖片高度。
let loadImgHeights = (imgs) => { return new Promise((resolve, reject) => { const length = imgs.length const heights = [] let count = 0 const load = (index) => { let img = new Image() const checkIfFinished = () => { count++ if (count === length) { resolve(heights) } } img.onload = () => { const ratio = img.height / img.width const halfHeight = ratio * halfInnerWidth // 高度按屏幕一半的比例來計算 heights[index] = halfHeight checkIfFinished() } img.onerror = () => { heights[index] = 0 checkIfFinished() } img.src = imgs[index] } imgs.forEach((img, index) => load(index)) }) } 複製代碼
有了圖片高度以後，我們就開始挑選適合這個需求的演算法了。
貪心演算法
在人的腦海中最直觀的想法是什麼樣的？在每裝一個圖片前都對比一下左右數組的高度和，往高度較小的那個數組裡去放入下一項。
這就是貪心演算法，我們來簡單實現下：
let greedy = (heights) => { let mid = Math.round(sum(heights) / 2) let total = 0 let leftHeights = [] let rightHeights = [] let left = [] let right = [] heights.forEach((height, index) => { if (sum(leftHeights) > sum(rightHeights)) { right.push(index) rightHeights.push(height) } else { left.push(index) leftHeights.push(height) } total += height }) return { left, right } } 複製代碼
我們得到了 left，right 數組，對應左右兩列渲染圖片的下標，並且我們也有了每個圖片的高度，那麼渲染到頁面上就很簡單了：
<div class="wrap" v-if="imgsLoaded"> <div class="half"> <img class="img" v-for="leftIndex in leftImgIndexes" :src="imgs[leftIndex]" :style="{ width: '100%', height: imgHeights[leftIndex] + 'px' }" /> </div> <div class="half"> <img class="img" v-for="rightIndex in rightImgIndexes" :src="imgs[rightIndex]" :style="{ width: '100%', height: imgHeights[rightIndex] + 'px' }" /> </div> </div> 複製代碼
貪心演算法只尋求局部最優解（只在考慮當前圖片的時候找到一個最優解），所以最後左右兩邊的高度差還是相對較大的，局部最優解很難成為全局最優解。
“大清亡於閉關鎖國，學習技術需要交流和資料”。 在這裡我給大家準備了很多的學習資料免費獲取,包括但不限於技術乾貨、大廠面試題系列、技術動向、職業生涯等一切有關程式員的分享.
web前端小白進階方法筆記,學習資料,面試題和視頻,項目源碼免費領取，通過努力追到自己的女神，走向人生巔峰
動態規劃
和局部最優解對應的是全局最優解，而說到全局最優解，我們很難不想到動態規劃這種演算法。它是求全局最優解的一個利器。
動態規劃中有一個很著名的問題：「01 背包問題」，題目的意思是這樣的：
有 n 個物品，它們有各自的體積和價值，現有給定容量的背包，如何讓背包里裝入的物品具有最大的價值總和？
那麼 01 背包問題和這個瀑布流演算法有什麼關係呢？這個思路確實比較難找，但是我們仔細想一下，假設我們有 [1, 2, 3] 這 3 個圖片高度的數組，我們怎麼通過轉化成 01 背包問題呢？
由於我們要湊到的是圖片總高度的一半，也就是 (1 + 2 + 3) / 2 = 3，那麼我們此時就有了一個 容量為3 的背包，而由於我們裝進左列中的圖片高度需要低於總高度的一半，待裝進背包的物體的總重量和高度是相同的 [1, 2, 3]。
那麼這個問題也就轉化為了，在 容量為3的背包 中，儘可能的從重量為 [1, 2, 3]，並且價值也為 [1, 2, 3] 的物品中，儘可能的挑選出總價值最大的物品集合裝進背包中。
也就是 總高度為3，在 [1, 2, 3] 這幾種高度的圖片中，儘可能挑出 總和最大，但是又小於3 的圖片集合，裝進數組中。
二維數組結構
我們構建的二維 dp 數組
縱坐標 y 是：當前可以考慮的圖片，比如 dp[0] 是只考慮下標為 0 的圖片，dp[1] 是考慮下標為 0 的圖片，並且考慮下標為 1 的圖片，以此類推，取值範圍是 0 ~ 圖片數組的長度 - 1。
橫坐標 x 是：用當前考慮的圖片集合，去儘可能湊到總高度為 y 時，所能湊成的最大高度 max，以及當前所使用的圖片下標集合 indexes，取值範圍是 0 ~ 高度的一半。
小問題拆解
就以 [1, 4, 5, 4] 這四張圖片高度為例，高度的一半是 7，用肉眼可以看出最接近 7 的子數組是[1, 5]，我們來看看動態規劃是怎麼求出這個結果的。
我們先看縱坐標為 0，也就是只考慮圖片 1 的情況：
-
首先去嘗試湊高度
1：我們知道圖片 1 的高度正好是 1，所以此時dp[0][0]所填寫的值是{ max: 1, indexes: [0] }，也就代表用總高度還剩 1，並且只考慮圖片 1 的情況下，我們的最優解是選用第一張圖片。 -
湊高度
2 ~ 7：由於當前只有 1 可以選擇，所以最優解只能是選擇第一張圖片，它們都是{ max: 1, indexes: [0] }。
高度 1 2 3 4 5 6 7
圖片1(h=1) 1 1 1 1 1 1 1
複製代碼
這一層在動態規劃中叫做基礎狀態，它是最小的子問題，它不像後面的縱坐標中要考慮多張圖片，而是只考慮單張圖片，所以一般來說都會在一層迴圈中單獨把它求解出來。
這裡我們還要考慮第一張圖片的高度大於我們要求的總高度的情況，這種情況下需要把 max 置為 0，選擇的圖片項也為空。
let mid = Math.round(sum(heights) / 2) let dp = [] // 基礎狀態 只考慮第一個圖片的情況 dp[0] = [] for (let cap = 0; cap <= mid; cap++) { dp[0][cap] = heights[0] > cap ? { max: 0, indexes: [] } : { max: heights[0], indexes: [0] } } 複製代碼
有了第一層的基礎狀態後，我們就可以開始考慮多張圖片的情況了，現在來到了縱坐標為 1，也就是考慮圖片 1 和考慮圖片 2 時求最優解：
高度 1 2 3 4 5 6 7
圖片1(h=1) 1 1 1 1 1 1 1
圖片2(h=2)
複製代碼
此時問題就變的有些複雜了，在多張圖片的情況下，我們可以有兩種選擇：
-
選擇當前圖片，那麼假設當前要湊的總高度為 3，當前圖片的高度為 2，剩餘的高度就為 1，此時我們可以用剩餘的高度去「上一個縱坐標」里尋找「只考慮前面幾種圖片」的情況下，高度為 1 時的最優解。並且記錄
當前圖片的高度 + 前幾種圖片湊剩餘高度的最優解為max1。 -
不選擇當前圖片，那麼就直接去「只考慮前面幾種圖片」的上一個縱坐標里，找到當前高度下的最優解即可，記為
max2。 -
比較
max1和max2，找出更大的那個值，記錄為當前狀態下的最優解。
有了這個前置知識，來繼續分解這個問題，在縱坐標為 1 的情況下，我們手上可以選擇的圖片有圖片 1 和圖片 2：
-
湊高度 1：由於圖片 2 的高度為 2，相當於是容量超了，所以這種情況下不選擇圖片 2，而是直接選擇圖片 1，所以
dp[1][0]可以直接沿用dp[0][0]的最優解，也就是{ max: 1, indexes: [0] }。 -
湊高度 2：
-
選擇圖片 2，圖片 2 的高度為 4，能夠湊成的高度為 4，已經超出了當前要湊的高度 2，所以不能選則圖片 2。
-
不選擇圖片 2，在只考慮圖片 1 時的最優解數組
dp[0]中找到高度為 2 時的最優解：dp[0][2]，直接沿用下來，也就是{ max: 1, indexes: [0] } -
這種情況下只能不選擇圖片 2，而沿用只選擇圖片 1 時的解，
{ max: 1, indexes: [0] }
-
-
省略湊高度
3 ~ 4的情況，因為得出的結果和湊高度 2 是一樣的。 -
湊高度 5：高度為 5 的情況下就比較有意思了：
-
選擇圖片 2，圖片 2 的高度為 4，能夠湊成的高度為 4，此時剩餘高度是 1，再去只考慮圖片 1 的最優解數組
dp[0]中找高度為 1 時的最優解dp[0][1]，發現結果是{ max: 1, indexes: [0] }，這兩個高度值 4 和 1 相加後沒有超出高度的限制，所以得出最優解：{ max: 5, indexes: [0, 1] } -
不選擇圖片 2，在圖片 1 的最優解數組中找到高度為 5 時的最優解：
dp[0][5]，直接沿用下來，也就是{ max: 1, indexes: [0] } -
很明顯選擇圖片 2 的情況下，能湊成的高度更大，所以
dp[1][2]的最優解選擇{ max: 5, indexes: [0, 1] }
-
仔細理解一下，相信你可以看出動態規劃的過程，從最小的子問題 只考慮圖片1出發，先求出最優解，然後再用子問題的最優解去推更大的問題 考慮圖片1、2、考慮圖片1、2、3的最優解。
畫一下[1,4,5,4]問題的 dp 狀態表吧：
可以看到，和我們剛剛推論的結果一致，在考慮圖片 1 和圖片 2 的情況下，湊高度為 5，也就是dp[1][5]的位置的最優解就是 5。最右下角的 dp[3][7] 就是考慮所有圖片的情況下，湊高度為 7 時的全局最優解。
給出代碼：
// 儘可能選出圖片中高度最接近圖片總高度一半的元素 let dpHalf = (heights) => { let mid = Math.round(sum(heights) / 2) let dp = [] // 基礎狀態 只考慮第一個圖片的情況 dp[0] = [] for (let cap = 0; cap <= mid; cap++) { dp[0][cap] = heights[0] > cap ? { max: 0, indexes: [] } : { max: heights[0], indexes: [0] } } for ( let useHeightIndex = 1; useHeightIndex < heights.length; useHeightIndex++ ) { if (!dp[useHeightIndex]) { dp[useHeightIndex] = [] } for (let cap = 0; cap <= mid; cap++) { let usePrevHeightDp = dp[useHeightIndex - 1][cap] let usePrevHeightMax = usePrevHeightDp.max let currentHeight = heights[useHeightIndex] // 這裡有個小坑 剩餘高度一定要轉化為整數 否則去dp數組裡取到的就是undefined了 let useThisHeightRestCap = Math.round(cap - heights[useHeightIndex]) let useThisHeightPrevDp = dp[useHeightIndex - 1][useThisHeightRestCap] let useThisHeightMax = useThisHeightPrevDp ? currentHeight + useThisHeightPrevDp.max : 0 // 是否把當前圖片納入選擇 如果取當前的圖片大於不取當前圖片的高度 if (useThisHeightMax > usePrevHeightMax) { dp[useHeightIndex][cap] = { max: useThisHeightMax, indexes: useThisHeightPrevDp.indexes.concat(useHeightIndex), } } else { dp[useHeightIndex][cap] = { max: usePrevHeightMax, indexes: usePrevHeightDp.indexes, } } } } return dp[heights.length - 1][mid] } 複製代碼
有了一側的數組以後，我們只需要在數組中找出另一半，即可渲染到屏幕的兩列中：
this.leftImgIndexes = dpHalf(imgHeights).indexes this.rightImgIndexes = omitByIndexes(this.imgs, this.leftImgIndexes) 複製代碼
優化 1
由於縱軸的每一層的最優解都只需要參考上一層節點的最優解，因此可以只保留兩行。通過判斷除 2 取餘來決定“上一行”的位置。此時空間複雜度是 O(2n)
由於每次參考值都只需要取上一行和當前位置左邊位置的值（因為減去了當前高度後，剩餘高度的最優解一定在左邊），因此 dp 數組可以只保留一行，把問題轉為從右向左求解，並且在求解的過程中不斷覆蓋當前的值，而不會影響下一次求解。此時空間複雜度是 O(n)。
並且在這種情況下對於時間複雜度也可以做優化，由於優化後，求當前高度的最優解是倒序遍歷的，那麼當發現求最優解的高度小於當前所考慮的那個圖片的的高度時，說明本次求解不可能考慮當前圖片了，此時左邊的高度的最優解一定是「上一行的最優解」。
