2865. 美丽塔 I

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

题目描述

给你一个长度为 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，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。