打卡记录

美丽塔 II（前后缀分解 + 单调栈）

链接

大佬的题解

class Solution:def maximumSumOfHeights(self, a: List[int]) -> int:n = len(a)suf = [0] * (n + 1)st = [n]  # 哨兵s = 0for i in range(n - 1, -1, -1):x = a[i]while len(st) > 1 and x <= a[st[-1]]:j = st.pop()s -= a[j] * (st[-1] - j)  # 撤销之前加到 s 中的s += x * (st[-1] - i)  # 从 i 到 st[-1]-1 都是 xsuf[i] = sst.append(i)ans = sst = [-1]  # 哨兵pre = 0for i, x in enumerate(a):while len(st) > 1 and x <= a[st[-1]]:j = st.pop()pre -= a[j] * (j - st[-1])  # 撤销之前加到 pre 中的pre += x * (i - st[-1])  # 从 st[-1]+1 到 i 都是 xans = max(ans, pre + suf[i + 1])st.append(i)return ans