前言
瀑布流布局是前端領域中一個很常見的需求，由于圖片的高度是不一致的，所以在多列布局中默認布局下很難獲得滿意的排列，
我們的需求是，圖片高度不規律的情況下，在兩列布局中，讓左右兩側的圖片總高度盡可能的接近，這樣的布局會非常的美觀，
注意，本文的目的僅僅是討論演算法在前端中能如何運用，而不是說瀑布流的最佳解法是動態規劃，可以僅僅當做學習拓展來看，
分析
從預覽圖中可以看出，雖然圖片的高度是不定的，但是到了這個布局的最底部，左右兩張圖片是正好對齊的，這就是一個比較美觀的布局了，
那么怎么實作這個需求呢？從頭開始拆解，現在我們能拿到一組圖片陣列 [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 v-if="imgsLoaded"> <div > <img class="img" v-for="leftIndex in leftImgIndexes" :src="imgs[leftIndex]" :style="{ width: '100%', height: imgHeights[leftIndex] + 'px' }" /> </div> <div > <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)
優化 2
由于每次參考值都只需要取上一行和當前位置左邊位置的值（因為減去了當前高度后，剩余高度的最優解一定在左邊），因此 dp 陣列可以只保留一行，把問題轉為從右向左求解，并且在求解的程序中不斷覆寫當前的值，而不會影響下一次求解，此時空間復雜度是 O(n)，
并且在這種情況下對于時間復雜度也可以做優化，由于優化后，求當前高度的最優解是倒序遍歷的，那么當發現求最優解的高度小于當前所考慮的那個圖片的的高度時，說明本次求解不可能考慮當前圖片了，此時左邊的高度的最優解一定是「上一行的最優解」，
“大清亡于閉關鎖國，學習技術需要交流和資料”， 在這里我給大家準備了很多的學習資料免費獲取,包括但不限于技術干貨、大廠面試題系列、技術動向、職業生涯等一切有關程式員的分享.
web前端小白進階方法筆記,學習資料,面試題和視頻,專案原始碼免費領取，通過努力追到自己的女神，走向人生巔峰
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/75997.html
標籤：JavaScript
上一篇：2020年的前端該怎么學？