最大高度和的美丽塔 | 算法题解 | 二分查找与前缀和后缀和

最大高度和的美丽塔

给定一个长度为 n 下标从 0 开始的整数数组 maxHeights。

你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i，高度为 heights[i]。

如果以下条件满足，我们称这些塔是 美丽的：

1. 1 <= heights[i] <= maxHeights[i]
2. heights 是一个 山状数组。

如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山状数组：

• 对于所有 0 < j <= i，都有 heights[j - 1] <= heights[j]
• 对于所有 i <= k < n - 1，都有 heights[k + 1] <= heights[k]

请你返回满足美丽塔要求的方案中，高度和的最大值。

解题思路

首先，我们需要找到一个合适的高度数组 heights，使得 heights 是一个山状数组，并且满足 1 <= heights[i] <= maxHeights[i]。

我们可以使用二分查找来确定 heights 的值。对于每个位置 i，我们在 [1, maxHeights[i]] 的范围内进行二分查找，找到一个合适的高度 heights[i]，使得 heights 是一个山状数组。

在确定了 heights 后，我们需要计算满足美丽塔要求的方案中，高度和的最大值。由于 heights 是一个山状数组，所以高度和的最大值可以通过计算 heights 的前缀和和后缀和来得到。

具体步骤如下：

1. 初始化左右指针 left 和 right，分别指向 heights 的开头和结尾。
2. 初始化前缀和 preSum 和后缀和 sufSum，分别用来计算 heights 的前缀和和后缀和。
3. 初始化高度和的最大值 maxSum 为 0。
4. 对于每个位置 i，从 left 到 i 的范围内，我们可以选择高度不超过 heights[i] 的任意一个位置作为左塔的高度，从 i 到 right 的范围内，我们可以选择高度不超过 heights[i] 的任意一个位置作为右塔的高度。 我们可以通过 preSum 和 sufSum 数组来快速计算出满足条件的左塔和右塔的高度和。然后，我们更新高度和的最大值 maxSum。
5. 如果左塔的高度小于右塔的高度，我们向左移动左指针 left；否则，我们向右移动右指针 right。
6. 重复步骤 4 和步骤 5，直到左指针和右指针相遇。
7. 返回高度和的最大值 maxSum。

时间复杂度分析

对于每个位置 i，二分查找的时间复杂度为 O(log(maxHeights[i]))，总共有 n 个位置，所以二分查找的总时间复杂度为 O(n * log(maxHeights[i]))。

计算前缀和和后缀和的时间复杂度为 O(n)，所以总时间复杂度为 O(n * log(maxHeights[i]))。

空间复杂度分析

我们需要额外使用两个数组 preSum 和 sufSum 来保存 heights 的前缀和和后缀和，所以空间复杂度为 O(n)。