说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。
题目描述
给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。
你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ,高度为 heights[i] 。
如果以下条件满足,我们称这些塔是 美丽 的:
1 <= heights[i] <= maxHeights[i]
heights 是一个 山脉 数组。
如果存在下标 i 满足以下条件,那么我们称数组 heights 是一个 山脉 数组:
对于所有 0 < j <= i ,都有 heights[j - 1] <= heights[j]
对于所有 i <= k < n - 1 ,都有 heights[k + 1] <= heights[k]
请你返回满足 美丽塔 要求的方案中,高度和的最大值 。
示例 1:
输入:maxHeights = [5,3,4,1,1] 输出:13 解释:和最大的美丽塔方案为 heights = [5,3,3,1,1] ,这是一个美丽塔方案,因为: - 1 <= heights[i] <= maxHeights[i] - heights 是个山脉数组,峰值在 i = 0 处。 13 是所有美丽塔方案中的最大高度和。
示例 2:
输入:maxHeights = [6,5,3,9,2,7] 输出:22 解释: 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ,这是一个美丽塔方案,因为: - 1 <= heights[i] <= maxHeights[i] - heights 是个山脉数组,峰值在 i = 3 处。 22 是所有美丽塔方案中的最大高度和。
示例 3:
输入:maxHeights = [3,2,5,5,2,3] 输出:18 解释:和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ,这是一个美丽塔方案,因为: - 1 <= heights[i] <= maxHeights[i] - heights 是个山脉数组,最大值在 i = 2 处。 注意,在这个方案中,i = 3 也是一个峰值。 18 是所有美丽塔方案中的最大高度和。
提示:
- 1 <= n == maxHeights <= 10^3
- 1 <= maxHeights[i] <= 10^9
解题思路
这题目数据规模比较小,我们可以直接使用前缀和+后缀和来解题。
const arr1 = new Array(maxHeights.length).fill(0); const len = maxHeights.length; map[maxHeights[0]] = 1; for (let i = 1; i < len; i++) { const n = map[maxHeights[i]] || 0; map[maxHeights[i]] = n + 1; let appendNum = 0; if (maxHeights[i] < maxHeights[i - 1]) { appendNum = checkMap(maxHeights[i]); } arr1[i] = arr1[i - 1] + appendNum; }
从左往右计算最大高度差的部分。首先创建一个长度为 maxHeights 的数组 arr1,用于记录从左边开始的最大高度差。然后使用一个 map 对象记录当前高度出现的次数。接下来遍历给定的高度数组 maxHeights,对于当前高度,如果其比前一个高度要低,则调用 checkMap 函数计算当前位置之前的最大高度差并将结果保存在 appendNum 中。最后将 appendNum 加到 arr1 数组中,更新 arr1 的值。
值得注意的是,由于第一个元素没有前面的元素与其比较,因此在初始化 map 对象时将 maxHeights[0] 的值设为 1 以表示该高度出现了一次。
其中 n 变量表示当前高度在 map 对象中出现的次数。如果 n 不存在,则默认为 0。
const arr2 = new Array(maxHeights.length).fill(0); const len = maxHeights.length; map = {}; map[maxHeights[len - 1]] = 1; let res = arr1[len - 1] + arr2[len - 1]; let sum = maxHeights[len - 1]; for (let i = len - 2; i >= 0; i--) { const n = map[maxHeights[i]] || 0; map[maxHeights[i]] = n + 1; let appendNum = 0; if (maxHeights[i] < maxHeights[i + 1]) { appendNum = checkMap(maxHeights[i]); } arr2[i] = arr2[i + 1] + appendNum; res = Math.min(arr1[i] + arr2[i], res); sum += maxHeights[i]; }
从右往左计算最大高度差的部分。首先创建一个长度为 maxHeights 的数组 arr2,用于记录从右边开始的最大高度差。然后初始化 map 对象,将最后一个元素的值设为 1 表示该高度出现了一次。然后初始化 res 变量为 arr1[len - 1] + arr2[len - 1],表示当前的最小值。
接下来倒序遍历给定的高度数组 maxHeights,对于当前高度,如果其比后一个高度要低,则调用 checkMap 函数计算当前位置之后的最大高度差并将结果保存在 appendNum 中。然后将 appendNum 加到 arr2 数组中,更新 arr2 的值。
同时,在每次遍历时,计算当前位置的最小值并将其与 res 取最小值,并将结果存储在 res 变量中。最后计算所有高度的和并存储在 sum 变量中。
值得注意的是,在处理完最后一个元素后,下一次循环中的 i 值为 len - 2,所以需要在循环中进行一次判断。另外,在初始化 map 对象时需要将之前的对象清空,否则会影响计算结果。
const checkMap = (maxNum) => { let sum = 0; for (let k in map) { if (Number(k) > Number(maxNum)) { sum += (k - maxNum) * map[k]; let n = map[maxNum] || 0; map[maxNum] = n + map[k]; delete map[k]; } } return sum; };
计算高度差总和。
AC代码
/** * @param {number[]} maxHeights * @return {number} */ var maximumSumOfHeights = function (maxHeights) { const arr1 = new Array(maxHeights.length).fill(0); const arr2 = new Array(maxHeights.length).fill(0); const len = maxHeights.length; let map = {}; const checkMap = (maxNum) => { let sum = 0; for (let k in map) { if (Number(k) > Number(maxNum)) { sum += (k - maxNum) * map[k]; let n = map[maxNum] || 0; map[maxNum] = n + map[k]; delete map[k]; } } return sum; }; map[maxHeights[0]] = 1; for (let i = 1; i < len; i++) { const n = map[maxHeights[i]] || 0; map[maxHeights[i]] = n + 1; let appendNum = 0; if (maxHeights[i] < maxHeights[i - 1]) { appendNum = checkMap(maxHeights[i]); } arr1[i] = arr1[i - 1] + appendNum; } map = {}; map[maxHeights[len - 1]] = 1; let res = arr1[len - 1] + arr2[len - 1]; let sum = maxHeights[len - 1]; for (let i = len - 2; i >= 0; i--) { const n = map[maxHeights[i]] || 0; map[maxHeights[i]] = n + 1; let appendNum = 0; if (maxHeights[i] < maxHeights[i + 1]) { appendNum = checkMap(maxHeights[i]); } arr2[i] = arr2[i + 1] + appendNum; res = Math.min(arr1[i] + arr2[i], res); sum += maxHeights[i]; } return sum - res; };
公众号
关注公众号『前端也能这么有趣
』,获取更多有趣内容。
说在后面
🎉 这里是 JYeontu,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球 🏸 ,平时也喜欢写些东西,既为自己记录 📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解 🙇,写错的地方望指出,定会认真改进 😊,偶尔也会在自己的公众号『
前端也能这么有趣
』发一些比较有趣的文章,有兴趣的也可以关注下。在此谢谢大家的支持,我们下文再见 🙌。