前言:
当前兄弟们对“前端实现瀑布流动的方法有哪些”可能比较珍视,兄弟们都需要剖析一些“前端实现瀑布流动的方法有哪些”的相关知识。那么小编也在网摘上收集了一些有关“前端实现瀑布流动的方法有哪些””的相关内容,希望大家能喜欢,同学们一起来学习一下吧!前言
瀑布流布局是前端领域中一个很常见的需求,由于图片的高度是不一致的,所以在多列布局中默认布局下很难获得满意的排列。
我们的需求是,图片高度不规律的情况下,在两列布局中,让左右两侧的图片总高度尽可能的接近,这样的布局会非常的美观。
注意,本文的目的仅仅是讨论算法在前端中能如何运用,而不是说瀑布流的最佳解法是动态规划,可以仅仅当做学习拓展来看。
分析
总预览图中可以看出,虽然图片的高度是不定的,但是到了这个布局的最底部,左右两张图片是正好对齐的,这就是一个比较美观的布局了。
那么怎么实现这个需求呢?从头开始拆解,现在我们能拿到一组图片数组 [img1, img2, img3],我们可以通过一些方法得到它对应的高度 [1000, 2000, 3000],那么现在我们的目标就是能够计算出左右两列 left: [1000, 2000] 和 right: [3000] 这样就可以把一个左右等高的布局给渲染出来了。
准备工作
首先准备好小姐姐数组 SISTERS:
let SISTERS = [ ';, ';, ';, ';, ... 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> 复制代码
贪心算法只寻求局部最优解(只在考虑当前图片的时候找到一个最优解),所以最后左右两边的高度差还是相对较大的,局部最优解很难成为全局最优解。
“大清亡于闭关锁国,学习技术需要交流和资料” 这里小编是一个有着5年工作经验的前端工程师,关于web前端有许多的技术干货,包括但不限于各大厂的最新面试题系列、游戏项目源码、最新前端路线等。需要的伙伴可以私信我,
发送【前端资料】
就可以获取领取地址,免费送给大家。对于学习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)。
并且在这种情况下对于时间复杂度也可以做优化,由于优化后,求当前高度的最优解是倒序遍历的,那么当发现求最优解的高度小于当前所考虑的那个图片的的高度时,说明本次求解不可能考虑当前图片了,此时左边的高度的最优解一定是「上一行的最优解」。
“大清亡于闭关锁国,学习技术需要交流和资料” 这里小编是一个有着5年工作经验的前端工程师,关于web前端有许多的技术干货,包括但不限于各大厂的最新面试题系列、游戏项目源码、最新前端路线等。需要的伙伴可以私信我,
发送【前端资料】
就可以获取领取地址,免费送给大家。对于学习web前端有任何问题(学习方法,学习效率,如何就业)都可以问我。希望你也能凭自己的努力,成为下一个优秀的程序员,追到自己的女神,走向人生巅峰
标签: #前端实现瀑布流动的方法有哪些