Codeforces Round #622 (Div. 2) C2. Skyscrapers (hard version)
题意：
你是一名建筑工程师，现给出 n 幢建筑的预计建设高度，你想建成峰状，如：
1 2 3 2 1 → 1 2 3 2 1
1 2 3 1 2 → 1 2 3 1 1
8 10 6 → 8 10 6
10 6 8 → 10 6 6
问所有建筑的高度和最大为多少。
思路：
单调递增栈栈顶存储以当前点为峰的单侧最低高度下标，另存储以每个点为峰的左右最大高度和。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;const int M = 550000;ll a[M], l[M], r[M];int main()
{
int n; cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i]; stack<int> st; for (int i = 1; i <= n; i++)//递推每个点左侧的最大高度和
{
while (!st.empty() && a[st.top()] >= a[i]) st.pop();
if (st.empty()) l[i] = i * a[i];
else l[i] = l[st.top()] + (i - st.top()) * a[i];
st.push(i);
} while (!st.empty()) st.pop(); for (int i = n; i >= 1; i--)//递推每个点右侧的最大高度和
{
while (!st.empty() && a[st.top()] >= a[i]) st.pop();
if (st.empty()) r[i] = (n - i + 1) * a[i];
else r[i] = r[st.top()] + (st.top() - i) * a[i];
st.push(i);
} ll res = 0, id = 0;
for (int i = 1; i <= n; i++)//寻找最大高度和的峰点
{
ll tmp = l[i] + r[i] - a[i];
if (tmp > res) { res = tmp; id = i; }
} for (int i = id - 1; i >= 1; i--) a[i] = min(a[i], a[i + 1]);//摊平峰左侧
for (int i = id + 1; i <= n; i++) a[i] = min(a[i], a[i - 1]);//摊平峰右侧 for (int i = 1; i <= n; i++) cout << a[i] << " "; return 0;
}
代码参考自：knight_wang
