思路：
使用单调栈。
实现：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N = 500005; 5 ll a[N], l[N], r[N]; 6 int main() 7 { 8 int n; 9 while (cin >> n) 10 { 11 stack<int> st; 12 for (int i = 1; i <= n; i++) cin >> a[i]; 13 for (int i = 1; i <= n; i++) 14 { 15 while (!st.empty() && a[st.top()] >= a[i]) st.pop(); 16 if (st.empty()) l[i] = i * a[i]; 17 else l[i] = l[st.top()] + (i - st.top()) * a[i]; 18 st.push(i); 19 } 20 while (!st.empty()) st.pop(); 21 for (int i = n; i >= 1; i--) 22 { 23 while (!st.empty() && a[st.top()] >= a[i]) st.pop(); 24 if (st.empty()) r[i] = (n - i + 1) * a[i]; 25 else r[i] = r[st.top()] + (st.top() - i) * a[i]; 26 st.push(i); 27 } 28 ll res = 0, id = 0; 29 for (int i = 1; i <= n; i++) 30 { 31 ll tmp = l[i] + r[i] - a[i]; 32 if (tmp > res) { res = tmp; id = i; } 33 } 34 for (int i = id - 1; i >= 1; i--) a[i] = min(a[i], a[i + 1]); 35 for (int i = id + 1; i <= n; i++) a[i] = min(a[i], a[i - 1]); 36 for (int i = 1; i <= n; i++) cout << a[i] << " "; 37 cout << endl; 38 } 39 return 0; 40 }