LC 2866. 美丽塔 II

https://leetcode.cn/problems/beautiful-towers-ii/

这题前面一题是相同的题目，但是是更小的数据量，思路就是枚举每个点为最高点。这题数据量在10^5级别，所以没有办法使用枚举了。

大致思路也好办，就是尽可能使用之前的结果：

如果hs[i] >= hs[i-1] 的话，那么就是 st[i-1] + hs[i]
如果hs[i] < hs[i-1] 的话，那么就需要找到最近的一个点
- 这个点 hs[x] <= hs[i].
- 那么就是 st[x + hs[i] * (i - x) （这段使用hs[i]削平）

所以问题就怎么寻找这个点。这个点没有办法同时二叉树来维护，因为二叉树的关系只能选择一个进行保持：要么是value, 要么是position. 没有办法同时维持两个。所以下次遇到这类问题的话，二叉树还是早点放弃比较好。

最终解决办法还是需要维持一个堆栈，这个堆栈是递增的，value和position都是递增的。

class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        def compute(hs):
            left = [0] * len(hs)
            st = []
            for i in range(len(hs)):
                while st and hs[i] < hs[st[-1]]:
                    st.pop()
                if not st:
                    left[i] = hs[i] * (i + 1)
                else:
                    j = st[-1]
                    left[i] = left[j] + hs[i] * (i - j)
                st.append(i)
            return left

        left = compute(maxHeights)
        right = compute(maxHeights[::-1])
        right = right[::-1]
        DEBUG = False
        if DEBUG:
            print(maxHeights)
            print(left)
            print(right)
        ans = 0
        for i in range(len(maxHeights)):
            c = left[i] + right[i] - maxHeights[i]
            ans = max(ans, c)
        return ans