构建美丽塔的最优高度和:算法解析与代码实现

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

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

如果以下条件满足,我们称这些塔是‘美丽’的:

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

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

  1. 对于所有 0 < j <= i,都有 heights[j - 1] <= heights[j]
  2. 对于所有 i <= k < n - 1,都有 heights[k + 1] <= heights[k]

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

解题思路

首先,我们需要找到一个山峰的位置,即找到一个下标 i,使得 heights[i] 最大,并且 heights[i-1] <= heights[i] 并且 heights[i] >= heights[i+1]。

然后,我们可以分别从左边和右边向山峰位置扩展,找到左边和右边的最大高度,并将高度限制在 maxHeights[i] 范围内。

最后,我们将左边和右边的最大高度相加,即为满足‘美丽塔’要求的方案中,高度和的最大值。

具体实现步骤如下:

  1. 遍历 maxHeights 数组,找到最大高度的山峰位置 i。
  2. 从左边向山峰位置扩展,找到左边的最大高度 leftHeight,并将高度限制在 maxHeights[i] 范围内。
    • 初始化 leftHeight 为 0。
    • 从 i-1 开始向左遍历,直到遇到高度小于等于 leftHeight 或者到达数组左边界。
    • 如果遇到高度大于 leftHeight,将 leftHeight 更新为高度,并将 leftHeight 限制在 maxHeights[i] 范围内。
  3. 从右边向山峰位置扩展,找到右边的最大高度 rightHeight,并将高度限制在 maxHeights[i] 范围内。
    • 初始化 rightHeight 为 0。
    • 从 i+1 开始向右遍历,直到遇到高度小于等于 rightHeight 或者到达数组右边界。
    • 如果遇到高度大于 rightHeight,将 rightHeight 更新为高度,并将 rightHeight 限制在 maxHeights[i] 范围内。
  4. 返回 leftHeight + rightHeight,即为满足‘美丽塔’要求的方案中,高度和的最大值。

时间复杂度分析

遍历 maxHeights 数组需要 O(n) 的时间复杂度,从左边向右边扩展和从右边向左边扩展的过程中,每个元素最多被访问两次,因此时间复杂度也是 O(n)。

所以总的时间复杂度是 O(n)。

代码实现如下:

def maxHeight(heights, maxHeights):
    n = len(heights)
    maxIndex = heights.index(max(heights))
    
    leftHeight = 0
    for i in range(maxIndex-1, -1, -1):
        if heights[i] > leftHeight:
            leftHeight = min(heights[i], maxHeights[i])
    
    rightHeight = 0
    for i in range(maxIndex+1, n):
        if heights[i] > rightHeight:
            rightHeight = min(heights[i], maxHeights[i])
    
    return leftHeight + rightHeight

测试示例:

heights = [1, 3, 2, 4, 1]
maxHeights = [2, 1, 1, 1, 1]
print(maxHeight(heights, maxHeights))  # 输出 3

解释:

最大高度的山峰位置是下标 3,对应的高度是 4。

从左边向右边扩展,左边的最大高度是 3(下标 1 对应的最大高度是 1,但是小于等于 3),右边的最大高度是 1。

所以满足‘美丽塔’要求的方案中,高度和的最大值是 3。

构建美丽塔的最优高度和:算法解析与代码实现

原文地址: https://www.cveoy.top/t/topic/bEXm 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录