[python 刷题] 2866 Beautiful Towers II

刷题] 2866 Beautiful Towers II"/>

[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. 这是一个极端案例，另一个极端案例就是 ⛰️ 的顶端在末尾，整个数组都是呈上升趋势

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

也就是说：

• 存在 [ 0 , . . . , j − 1 , j ] [0, ..., j - 1, j] [0,...,j−1,j] 的区间，其中 n u m s [ j ] ≥ n u m s [ j − 1 ] ≥ . . . ≥ n u m s [ 0 ] nums[j] \ge nums[j - 1] \ge ... \ge nums[0] nums[j]≥nums[j−1]≥...≥nums[0]，其中 j > 0 j > 0 j>0

• 存在 [ j , j + 1 , . . . , k ] [j, j + 1, ..., k] [j,j+1,...,k] 的区间，其中 n u m s [ j ] ≥ n u m s [ j + 1 ] ≥ . . . ≥ n u m s [ k ] nums[j] \ge nums[j + 1] \ge ... \ge nums[k] nums[j]≥nums[j+1]≥...≥nums[k]，其中 j < = k = l e n ( n u m s ) − 1 j <= k = len(nums) - 1 j<=k=len(nums)−1

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

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

完整解题思路如下：

1. 新建一个 stack 存储遍历过值的下标，新建一个数组存储 l e f t s u m left_sum lefts​um 的值

2. 从 [ 0 , 1 , . . . , l e n ( n u m s ) − 1 ] [0, 1, ..., len(nums) - 1] [0,1,...,len(nums)−1] 遍历一遍数组

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

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

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

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

3. 从 [ l e n ( n u m s ) − 1 , l e n ( n u m s ) − 2 , . . . , 1 , 0 ] [len(nums) - 1, len(nums) - 2, ..., 1, 0] [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 作为山峰，结果如下：

   此时的结果为 m a x ( 0 , 17 + 7 − 7 ) max(0, 17 + 7 - 7) max(0,17+7−7)，之所以要 − 7 -7 −7 是因为 m a x H e i g h t s [ i ] maxHeights[i] maxHeights[i] 在 prefix 计算添加了一次，suffix 计算也添加了一次

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

   此时的结果为 m a x ( 17 , 10 + 4 − 2 ) max(17, 10 + 4 - 2) max(17,10+4−2)

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

   此时的结果为 m a x ( 17 , 18 + 13 − 9 ) max(17, 18 + 13 - 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…?