2866.美丽塔II

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

题解 1 - python

• 编辑时间：2023-12-21
• 执行用时：316ms
• 内存消耗：42.55MB
• 编程语言：python
• 解法介绍：字符串拼接。

class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        n = len(maxHeights)
        prev = [-1] * n
        next = [n] * n
        s = []
        for i in range(n):
            while s and maxHeights[s[-1]] >= maxHeights[i]: s.pop()
            if s: prev[i] = s[-1]
            s.append(i)
        s.clear()
        for i in range(n):
            while s and maxHeights[s[-1]] > maxHeights[i]: next[s.pop()] = i
            s.append(i)
        lsums = [0] * n
        rsums = [0] * n
        for i in range(n):
            lsums[i] += (i - prev[i]) * maxHeights[i]
            if prev[i] != -1: lsums[i] += lsums[prev[i]]
        for i in range(n - 1, -1, -1):
            rsums[i] += (next[i] - i) * maxHeights[i]
            if next[i] != n: rsums[i] += rsums[next[i]]
        return max(lsums[i] + rsums[i] - maxHeights[i] for i in range(n))