题目描述：
给你一个长度为 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\le n \le 10^5;1\le maxHeights[i] \le 10^9$
题解：
数据范围比较大，要想使得总高度最大，那么肯定是要取 $heights[i] = maxHeights[i]$ 。但是需要满足左侧递增右侧递减，因此每次碰到一个更低的，都需要修改之前的比他高的。
可以发现是单调栈，因为需要找低的，所以使用单调增栈，每次遇到一个更低的，都要弹出比他高的，然后减去贡献，加上低的贡献。
最后的答案是阶梯状的，每次遇到更低的就弹出一个阶梯，计算阶梯的宽度，宽度就是当前栈顶坐标减去弹出之后的栈顶坐标。最后加上更长的低一些的贡献。
为了简单，可以使用哨兵，在左侧加一个 $-1$ 下标作为哨兵，在反向单调栈中加一个 $n$ 下标作为哨兵。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
long long maximumSumOfHeights(vector<int> &maxHeights)
{
int n = maxHeights.size();
int top = -1;
vector<long long> dp1(n);
vector<long long> dp2(n);
vector<int> st(n);
long long sum = 0;
int pre_index, cur_index = -1;
for (int i = 0; i < n; ++i)
{
while (top >= 0 && maxHeights[st[top]] > maxHeights[i])
{
pre_index = st[top];
cur_index = -1;
--top;
if (top >= 0)
cur_index = st[top];
sum -= 1ll * (pre_index - cur_index) * maxHeights[pre_index];
}
if (top >= 0)
cur_index = st[top];
else
cur_index = -1;
sum += 1ll * (i - cur_index) * maxHeights[i];
st[++top] = i;
dp1[i] = sum;
}
top = -1;
sum = 0;
cur_index = n;
for (int i = n - 1; i >= 0; --i)
{
while (top >= 0 && maxHeights[st[top]] > maxHeights[i])
{
pre_index = st[top];
cur_index = n;
--top;
if (top >= 0)
cur_index = st[top];
sum -= 1ll * (cur_index - pre_index) * maxHeights[pre_index];
}
if (top >= 0)
cur_index = st[top];
else
cur_index = n;
sum += 1ll * (cur_index - i) * maxHeights[i];
st[++top] = i;
dp2[i] = sum;
}
long long ans = 0;
for (int i = 0; i < n; ++i)
{
ans = max(ans, dp1[i] + dp2[i] - maxHeights[i]);
}
return ans;
}
};
|