[python 刷题] 2866 Beautiful Towers II

[python 刷题] 2866 Beautiful Towers II

题目如下：

You are given a 0-indexed array maxHeights of n integers.

You are tasked with building n towers in the coordinate line. The ith tower is built at coordinate i and has a height of heights[i].

A configuration of towers is beautiful if the following conditions hold:

1. 1 <= heights[i] <= maxHeights[i]
2. heights is a mountain array.

Array heights is a mountain if there exists an index i such that:

• For all 0 < j <= i, heights[j - 1] <= heights[j]
• For all i <= k < n - 1, heights[k + 1] <= heights[k]

Return the maximum possible sum of heights of a beautiful configuration of towers.

这个 mountain 的定义，其实图解一下就很好理解了：

1. 

   这是一个极端案例，另一个极端案例就是 ⛰️ 的顶端在末尾，整个数组都是呈上升趋势

2. 

3. 

提炼一下就是，数组的结构大致如下：

也就是说：

• 存在 $[0,...,j-1,j]$ 的区间，其中 $nums[j]\ge nums[j-1]\ge ...\ge nums[0]$，其中 $j>0$

• 存在 $[j,j+1,...,k]$ 的区间，其中 $nums[j]\ge nums[j+1]\ge ...\ge nums[k]$，其中 $j<=k=len(nums)-1$

从图像上来说，这道题其实有点像 84 Largest Rectangle in Histogram，解题思路也是类似的(都是 monotonic stack)

而另一个方面 ，这道题求的又是高度之和，所以又是一个 prefix sum 的变种问题，也因此解题需要将这一部分考虑在其中

完整解题思路如下：

1. 新建一个 stack 存储遍历过值的下标，新建一个数组存储 $lef{t}_{s}um$ 的值

2. 从 $[0,1,...,len(nums)-1]$ 遍历一遍数组

   每次遍历的过程中都将当前值作为 ⛰️ 的顶点

   因此需要检查 stack 中的值，如果 nums[stack[-1]] 比当前大，就需要将从结果中移除前一座山峰与现在当前高度差

   同时将当前山峰的高度加上去

   完成循环后就能获得 📈 曲线的结果了

3. 从 $[len(nums)-1,len(nums)-2,...,1,0]$ 遍历一遍数组

   这是为了获取 ⛰️ 右侧下降的结果

   二者相加，并取最大值就能够获得最终的结果

以第二个 input [6,5,3,9,2,7] 为例跑一遍

1. 以数组中的第一个值 6 作为山峰

   这里 stack 的值应该是 stack:[0]，保存的是下标而不是值

   

2. 以数组中的第二个值 5 作为山峰

   这时候的山峰是没有前一座山峰高，因此对前一座山进行一下处理。这里处理方式比较粗暴，就是直接把前面的山给挖了，然后通过获取的下标，做一个反向延长，类似于 84 Largest Rectangle in Histogram 的操作。

   最后结果：

   

   这里 stack 中的值更新为正确的下标

3. 以数组中的第三个值 3 作为山峰

   同样需要反向延长的操作，结果：

   

4. 以数组中的第四个值 9 作为山峰

   9 作为山峰是可以更高的，因此这里没有对 stack 进行任何一个操作，结果如下：

   

5. 以数组中的第五个值 2 作为山峰

   

   这里就需要删减两次，最终获得：

   

   stack 我忘了更新了，不过这个循环也用不到 stack 就不补了

6. 以数组中的最后的值 7 作为山峰

   因为山峰是可以允许作为最高的存在，因此这里不需要做特殊的操作，直接更新 stack 和 left_sum 即可：

   

   stack 我忘了更新了，不过这个循环也用不到 stack 就不补了

到这里， prefix 的处理就做完了，接着反向做 suffix 的处理，逻辑也是一样的，重新初始化 stack 和高度，重新走一遍循环：

1. 以数组中的最后的值 7 作为山峰，结果如下：

   

   此时的结果为 $max(0,17+7-7)$，之所以要 $-7$ 是因为 $maxHeights[i]$ 在 prefix 计算添加了一次，suffix 计算也添加了一次

2. 以数组中的第四个值 7 作为山峰，结果如下：

   

   此时的结果为 $max(17,10+4-2)$

3. 以数组中的第三个值 9 作为山峰，结果如下：

   

   此时的结果为 $max(17,18+13-9)$

4. 以此类推…

最终代码如下：

class Solution:def maximumSumOfHeights(self, maxHeights):left_sum = [0 for _ in maxHeights]stack = [] # store [i, h]total = 0for i, h in enumerate(maxHeights):while stack and stack[-1][1] > h:j, j_h = stack.pop()multiplier = j - stack[-1][0] if stack else j + 1# 这里把所有高出当前峰的 ⛰️ 都从结果中扣掉total -= j_h * multiplier# 然后在加回去，这时候 stack 中如果存在值，那一定比当前 ⛰️ 要小# 如果 stack 为空，则代表当前 ⛰️ 可以一直延续到 i = 0multiplier = i - stack[-1][0] if stack else i + 1total += h * multiplierleft_sum[i] = totalstack.append([i, h])stack = []total = 0result = 0# 一个反向求解，从 len(maxHeights) - 1, ..., 0 的方向遍历# 其余操作与第一个 for loop 一致，唯一需要注意的就是这里的下标计算为# [j, j + 1, ..., len(maxHeights)]# 第一个 loop 中为# [0, 1, ..., j]for i in reversed(range(len(maxHeights))):while stack and maxHeights[stack[-1]] > maxHeights[i]:j = stack.pop()multiplier = stack[-1] - j if stack else len(maxHeights) - jtotal -= maxHeights[j] * multipliermultiplier = stack[-1] - i if stack else len(maxHeights) - itotal += maxHeights[i] * multiplierresult = max(result, total + left_sum[i] - maxHeights[i])stack.append(i)return result

讲道理我对 LC 的 rating 不是很理解……Largest Rectangle in Histogram(hard) + prefix sum = medium problem…?