Skip to content

Latest commit

 

History

History
121 lines (85 loc) · 4.23 KB

2866.beautiful-towers-ii.md

File metadata and controls

121 lines (85 loc) · 4.23 KB

题目地址(2866. 美丽塔 II)

https://leetcode.cn/problems/beautiful-towers-ii/description/

题目描述

给你一个长度为 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 <= 105
1 <= maxHeights[i] <= 109

前置知识

  • 动态规划
  • 单调栈

思路

这是一个为数不多的 2000 多分的中等题,难度在中等中偏大。

枚举 i 作为顶峰,其取值贪心的取 maxHeight[i]。关键是左右两侧如何取。由于左右两侧逻辑没有本质区别, 不妨仅考虑左边,然后套用同样的方法处理右边。

定义 f[i] 表示 i 为峰顶,左侧高度和最大值。我们可以递推地计算出所有 f[i] 的值。同理 g[i] 表示 i 为峰顶,右侧高度和最大值。

当 f 和 g 都已经处理好了,那么枚举 f[i] + g[i] - maxHeight[i] 的最大值即可。之所以减去 maxHeight[i] 是因为 f[i] 和 g[i] 都加上了当前位置的高度 maxHeight[i],重复了。

那么现在剩下如何计算 f 数组,也就是递推公式是什么。

我们用一个单调栈维护处理过的位置,对于当前位置 i,假设其左侧第一个小于它的位置是 l,那么 [l + 1, i] 都是大于等于 maxHeight[i] 的, 都可以且最多取到 maxHeight[i]。可以得到递推公式 f[i] = f[l] + (i - l) * maxHeight[i]

代码

  • 语言支持:Python3

Python3 Code:

class Solution:
    def maximumSumOfHeights(self, maxHeight: List[int]) -> int:
        # 枚举 i 作为顶峰,其取值贪心的取 maxHeight[i]
        # 其左侧第一个小于它的位置 l,[l + 1, i] 都可以且最多取到 maxHeight[i]
        n = len(maxHeight)
        f = [-1] * n # f[i] 表示 i 为峰顶,左侧高度和最大值
        g = [-1] * n # g[i] 表示 i 为峰顶,右侧高度和最大值
        def cal(f):
            st = []
            for i in range(len(maxHeight)):
                while st and maxHeight[i] < maxHeight[st[-1]]:
                    st.pop()
                # 其左侧第一个小于它的位置 l,[l + 1, i] 都可以且最多取到 maxHeight[i]
                if st:
                    f[i] = (i - st[-1]) * maxHeight[i] + f[st[-1]]
                else:
                    f[i] = maxHeight[i] * (i + 1)
                st.append(i)
        cal(f)
        maxHeight = maxHeight[::-1]
        cal(g)
        maxHeight = maxHeight[::-1]
        ans = 0
        for i in range(len(maxHeight)):
            ans = max(ans, f[i] + g[n - 1 - i] - maxHeight[i])
        return ans

复杂度分析

令 n 为数组长度

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(n)$

f 和 g 以及 st 都使用 n 的空间。并且我们仅遍历了 maxHeights 数组三次,因此时间和空间复杂度都是 n。