[python 刷题] 2866 Beautiful Towers II

[python 刷题] 2866 Beautiful Towers II

题目如下：

这个

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

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

到这里， 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 = 0
        for 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 = 0
            multiplier = i - stack[-1][0] if stack else i + 1

            total += h * multiplier
            left_sum[i] = total
            stack.append([i, h])

        stack = []
        total = 0
        result = 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) - j
                total -= maxHeights[j] * multiplier

            multiplier = stack[-1] - i if stack else len(maxHeights) - i
            total += maxHeights[i] * multiplier

            result = max(result, total + left_sum[i] - maxHeights[i])
            stack.append(i)

        return result

---

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