Leetcode 2866. Beautiful Towers II

• Leetcode 2866. Beautiful Towers II
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：2866. Beautiful Towers II

1. 解题思路

这一题其实思路上还是比较明显的，就是一个单调数组的问题，问题在于说如果具体去设计这个单调数组。

我们从题目出发，具体来说，就是要构造一个山形数组，使得这个山形数组在给定的maxHeights的限制下能够面积最大，或者说累积和最大。

那么，我们不妨考察每一个位置作为山的山顶的情况下所能够构成的山形数组的面积，然后取出其中的最大值即可。

而这个问题又可以进一步拆解为，考察每一个位置作为山顶时，其左侧可以获得最大面积以及右侧可以获得的最大面积。此时，前者就是一个单调非减数组，而后者就是一个单调非增数组。而这两部分本质上又是相同的，因此，我们仅以左侧进行说明。

要求每一个位置作为山顶时左侧的这个最大的单调非增数组，那么对应可以采用的maxHeights一定也是一个单调递增的数组，因此，我们只需要构造一个数组，考察每一个位置的maxHeight[i]时，就弹出当前单调数组当中所有大于这个高度的值，直到剩下有一个更低的maxHeight[j]存在，此时能够获得的面积就是之前一个maxHeight[j]的面积加上maxHeight[i]*(i-j)，也就是从第j+1到i的位置最多只能够取maxHeight[i]，从而，我们就在$O(N)$的时间复杂度上求得了所有位置作为山顶时，左侧可以取到的最大面积。

同样，我们反向即可求得右侧的最大面积，两者相加减去其本身（因为本身计算了两次）即为对应位置作为山顶时能够取到的最大面积。

最后，我们再从中获得最大值即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        n = len(maxHeights)
        
        left = [0 for _ in range(n)]
        s = []
        for i, h in enumerate(maxHeights):
            while s != [] and s[-1][0] >= h:
                s.pop()
            if s == []:
                s.append((h, i, h*(i+1)))
            else:
                _, j, r = s[-1]
                s.append((h, i, r + h*(i-j)))
            left[i] = s[-1][2]
        
        right = [0 for _ in range(n)]
        s = []
        for i in range(n-1, -1, -1):
            h = maxHeights[i]
            while s != [] and s[-1][0] >= h:
                s.pop()
            if s == []:
                s.append((h, i, h*(n-i)))
            else:
                _, j, r = s[-1]
                s.append((h, i, r + h*(j-i)))
            right[i] = s[-1][2]
        
        return max(left[i] + right[i] - maxHeights[i] for i in range(n))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

提交代码评测得到：耗时862ms，占用内存42.5MB。