2865.美丽塔I

链接：2865.美丽塔I
难度：Medium
标签：栈、数组、单调栈
简介：请你返回满足 美丽塔 要求的方案中，高度和的最大值 。

题解 1 - python

• 编辑时间：2024-01-24
• 执行用时：41ms
• 内存消耗：16.82MB
• 编程语言：python
• 解法介绍：单调栈。

class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        n = len(maxHeights)
        s = []
        larr = [-1] * n
        rarr = [n] * n
        for i in range(n):
            while s and maxHeights[s[-1]] >= maxHeights[i]: rarr[s.pop()] = i
            if s: larr[i] = s[-1]
            s.append(i)
        lh = [0] * (n + 2)
        rh = [0] * (n + 2)
        for i in range(n):
            lh[i + 1] = maxHeights[i] * (i - larr[i]) + lh[larr[i] + 1]
        for i in range(n - 1, -1, -1):
            rh[i + 1] = maxHeights[i] * (rarr[i] - i) + rh[rarr[i] + 1]
        return max(lh[i + 1] + rh[i + 1] - maxHeights[i] for i in range(n))