class Solution {
public:
long long maximumSumOfHeights(vector<int>& maxHeights) {
}
};
100049. 美丽塔 I
给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。
你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。
如果以下条件满足，我们称这些塔是 美丽 的：
1 <= heights[i] <= maxHeights[i]heights 是一个 山状 数组。如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山状 数组：
0 < j <= i ，都有 heights[j - 1] <= heights[j]i <= k < n - 1 ，都有 heights[k + 1] <= heights[k]请你返回满足 美丽塔 要求的方案中，高度和的最大值 。
示例 1：
输入：maxHeights = [5,3,4,1,1] 输出：13 解释：和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为： - 1 <= heights[i] <= maxHeights[i] - heights 是个山状数组，峰值在 i = 0 处。 13 是所有美丽塔方案中的最大高度和。
示例 2：
输入：maxHeights = [6,5,3,9,2,7] 输出：22 解释： 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ，这是一个美丽塔方案，因为： - 1 <= heights[i] <= maxHeights[i] - heights 是个山状数组，峰值在 i = 3 处。 22 是所有美丽塔方案中的最大高度和。
示例 3：
输入：maxHeights = [3,2,5,5,2,3] 输出：18 解释：和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ，这是一个美丽塔方案，因为： - 1 <= heights[i] <= maxHeights[i] - heights 是个山状数组，最大值在 i = 2 处。 注意，在这个方案中，i = 3 也是一个峰值。 18 是所有美丽塔方案中的最大高度和。
提示：
1 <= n == maxHeights <= 1031 <= maxHeights[i] <= 109原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 4.5 MB, 提交时间: 2023-09-24 22:48:31
func maximumSumOfHeights(a []int) int64 {
ans := 0
n := len(a)
suf := make([]int, n+1)
st := []int{n} // 哨兵
sum := 0
for i := n - 1; i >= 0; i-- {
x := a[i]
for len(st) > 1 && x <= a[st[len(st)-1]] {
j := st[len(st)-1]
st = st[:len(st)-1]
sum -= a[j] * (st[len(st)-1] - j) // 撤销之前加到 sum 中的
}
sum += x * (st[len(st)-1] - i) // 从 i 到 st[len(st)-1]-1 都是 x
suf[i] = sum
st = append(st, i)
}
ans = sum
st = []int{-1} // 哨兵
pre := 0
for i, x := range a {
for len(st) > 1 && x <= a[st[len(st)-1]] {
j := st[len(st)-1]
st = st[:len(st)-1]
pre -= a[j] * (j - st[len(st)-1]) // 撤销之前加到 pre 中的
}
pre += x * (i - st[len(st)-1]) // 从 st[len(st)-1]+1 到 i 都是 x
ans = max(ans, pre+suf[i+1])
st = append(st, i)
}
return int64(ans)
}
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 16 ms, 内存消耗: 25.6 MB, 提交时间: 2023-09-24 22:48:19
class Solution {
public:
long long maximumSumOfHeights(vector<int> &a) {
int n = a.size();
vector<long long> suf(n + 1);
stack<int> st;
st.push(n); // 哨兵
long long sum = 0;
for (int i = n - 1; i >= 0; i--) {
int x = a[i];
while (st.size() > 1 && x <= a[st.top()]) {
int j = st.top();
st.pop();
sum -= (long long) a[j] * (st.top() - j); // 撤销之前加到 sum 中的
}
sum += (long long) x * (st.top() - i); // 从 i 到 st.top()-1 都是 x
suf[i] = sum;
st.push(i);
}
long long ans = sum;
st = stack<int>();
st.push(-1); // 哨兵
long long pre = 0;
for (int i = 0; i < n; i++) {
int x = a[i];
while (st.size() > 1 && x <= a[st.top()]) {
int j = st.top();
st.pop();
pre -= (long long) a[j] * (j - st.top()); // 撤销之前加到 pre 中的
}
pre += (long long) x * (i - st.top()); // 从 st.top()+1 到 i 都是 x
ans = max(ans, pre + suf[i + 1]);
st.push(i);
}
return ans;
}
};
java 解法, 执行用时: 8 ms, 内存消耗: 42 MB, 提交时间: 2023-09-24 22:48:05
class Solution {
public long maximumSumOfHeights(List<Integer> maxHeights) {
int[] a = maxHeights.stream().mapToInt(i -> i).toArray();
int n = a.length;
long[] suf = new long[n + 1];
var st = new ArrayDeque<Integer>();
st.push(n); // 哨兵
long sum = 0;
for (int i = n - 1; i >= 0; i--) {
int x = a[i];
while (st.size() > 1 && x <= a[st.peek()]) {
int j = st.pop();
sum -= (long) a[j] * (st.peek() - j); // 撤销之前加到 sum 中的
}
sum += (long) x * (st.peek() - i); // 从 i 到 st.peek()-1 都是 x
suf[i] = sum;
st.push(i);
}
long ans = sum;
st.clear();
st.push(-1); // 哨兵
long pre = 0;
for (int i = 0; i < n; i++) {
int x = a[i];
while (st.size() > 1 && x <= a[st.peek()]) {
int j = st.pop();
pre -= (long) a[j] * (j - st.peek()); // 撤销之前加到 pre 中的
}
pre += (long) x * (i - st.peek()); // 从 st.peek()+1 到 i 都是 x
ans = Math.max(ans, pre + suf[i + 1]);
st.push(i);
}
return ans;
}
}
python3 解法, 执行用时: 96 ms, 内存消耗: 16.3 MB, 提交时间: 2023-09-24 22:47:52
'''
前后缀分解+单调栈
计算从 a[0] 到 a[i] 形成山状数组的左侧递增段，元素和最大是多少，记到数组 pre[i] 中。
计算从 a[i] 到 a[n−1] 形成山状数组的右侧递减段，元素和最大是多少，记到数组 suf[i] 中。
那么答案就是 pre[i]+suf[i+1] 的最大值。
'''
class Solution:
def maximumSumOfHeights(self, a: List[int]) -> int:
n = len(a)
suf = [0] * (n + 1)
st = [n] # 哨兵
s = 0
for 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 都是 x
suf[i] = s
st.append(i)
ans = s
st = [-1] # 哨兵
pre = 0
for 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 都是 x
ans = max(ans, pre + suf[i + 1])
st.append(i)
return ans