2865. 美丽塔 I

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

目录
相关文章
|
6月前
|
JSON 数据格式
星系炸弹(蓝桥杯)
星系炸弹(蓝桥杯)
|
6月前
国王的魔镜
国王的魔镜
53 0
|
存储 人工智能 弹性计算
600天,我们在沙漠筑“城堡”
600天,我们在沙漠筑“城堡”
114 0
每日一题—— 太平洋大西洋水流问题
每日一题—— 太平洋大西洋水流问题
106 0
每日一题—— 太平洋大西洋水流问题
|
弹性计算 关系型数据库 MySQL
在知识的海洋里喝水
福建疫情来袭,宿舍上课之际。闲来无事为协会创建一个官网。以便后续纳新等后续各项事宜发布。试运营之后将接入学校官网。
在知识的海洋里喝水
如何在公共场合收拾熊孩子
首先,我要反驳一种流行的错误观点,就是认为孩子还小,还没有规则意识,所以孩子熊就让他们熊。这是错误的。3岁的孩子已经可以明白,承诺和合作的意义了,已经可以发展出合作精神了。
1160 0