说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。
题目描述
给你一个长度为 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，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『
前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。
