美丽塔 II

The given solution tries to find the maximum sum of heights for a mountain array configuration. First, it uses two arrays `pre` and `post` to store the maximum possible sum of heights from the start to the current index (for `pre`) and from the current index to the end (for `post`). The algorithm performs two passes over the `maxHeights` array. In the first pass (forward direction), it computes for each tower the maximum sum of heights from the start up to and including that tower, under the constraint that tower heights must not decrease. It uses a stack to maintain indices of towers such that the heights at these indices are in a non-decreasing order. This helps in efficiently computing the range sum by popping indices from the stack when the current tower height is less than the height at the top index of the stack. In the second pass (backward direction), it similarly computes the maximum sum of heights from each tower to the end of the array. Finally, for each tower, it combines these sums (subtracting the tower's height once because it's added in both `pre` and `post`), and tracks the maximum sum obtained. This maximum sum represents the highest sum of heights for a mountain array configuration.

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        n = len(maxHeights)
        pre = [0] * n  # Array to store max sum from start to i
        post = [0] * n  # Array to store max sum from i to end
        s = []  # Stack to maintain indices with non-decreasing maxHeights
        for i in range(n):
            while s and maxHeights[s[-1]] > maxHeights[i]:
                s.pop()  # Maintain non-decreasing order in stack
            if not s:
                pre[i] = (i+1)*maxHeights[i]  # Calculate sum from start to i if it's the smallest seen so far
            else:
                pre[i] = pre[s[-1]] + (i-s[-1]) * maxHeights[i]  # Calculate sum using previous values
            s.append(i)
        s = []
        res = 0
        for i in range(n-1, -1, -1):
            while s and maxHeights[s[-1]] > maxHeights[i]:
                s.pop()
            if not s:
                post[i] = (n-i) * maxHeights[i]  # Calculate sum from i to end if it's the smallest seen so far
            else:
                post[i] = post[s[-1]] + (s[-1]-i) * maxHeights[i]  # Calculate sum using previous values
            s.append(i)
            res = max(res, pre[i] + post[i] - maxHeights[i])  # Combine pre and post subtracting current height once
        return res