Skyscrapers (hard version)

思路：我们需要维护当下标为inx的大楼为最高的时候，两边大楼的情况。我们可以把下标为inx的大楼最高时，分别统计左边和右边的情况，我们可以用单调栈维护最小值（小->大），如果栈顶的元素的高度小于inx的大楼，说明之前的所有大楼都因为栈顶的大楼而小于了inx的大楼的高度，如果栈顶的大楼高度大于等于inx的大楼，则说明栈顶下面第一个的大楼到栈顶的大楼之间的大楼需要改变为inx大楼的高度，需要注意空栈的情况。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <functional>
  5 #include <set>
  6 #include <vector>
  7 #include <queue>
  8 #include <cstring>
  9 #include <stack>
 10  
 11 using namespace std;
 12  
 13 #define ll long long
 14 #define pb push_back
 15 #define fi first
 16 #define se second
 17  
 18  
 19 void solve(){
 20     int n;
 21     cin >> n;    
 22     vector<int > a(n);
 23     for(auto& in : a) cin >> in;
 24     stack<int > Sta;
 25     vector<ll > pre(n);
 26     for(int now = 0; now < n; ++now){
 27         while(!Sta.empty()){
 28             int top = Sta.top();
 29             if(a[top] >= a[now]){
 30                 Sta.pop();
 31                 if(!Sta.empty()){
 32                     pre[now] += (ll)a[now] * (top - (int)Sta.top());
 33                 }else {
 34                     pre[now] += (ll)a[now] * (top + 1);
 35                 }
 36             }else {
 37                 pre[now] += pre[top];
 38                 break;
 39             }
 40         }
 41         Sta.push(now);
 42         pre[now] += a[now];
 43     }
 44     // for(int i = 0; i < n; ++i) cout << pre[i] << " ";
 45     // cout << endl;
 46     vector<ll > rpre(n);
 47     while(!Sta.empty()) Sta.pop();
 48     vector<int > cp(a);
 49     reverse(a.begin(), a.end());
 50     for(int now = 0; now < n; ++now){
 51         while(!Sta.empty()){
 52             int top = Sta.top();
 53             if(a[top] >= a[now]){
 54                 Sta.pop();
 55                 if(!Sta.empty()){
 56                     rpre[now] += (ll)a[now] * (top - (int)Sta.top());
 57                 }else {
 58                     rpre[now] += (ll)a[now] * (top + 1);
 59                 }
 60             }else {
 61                 rpre[now] += rpre[top];
 62                 break;
 63             }
 64         }
 65         Sta.push(now);
 66         rpre[now] += a[now];
 67     }
 68     // for(auto& x : rpre) cout << x << " ";
 69     // cout << endl;
 70     int inx = 0;
 71     //cp[i]被算了两次，需要减去一次
 72     for(int i = 1; i < n; ++i){
 73         inx = (pre[i] + rpre[n - 1 - i] - cp[i] > pre[inx] + rpre[n - 1 - inx]  - cp[inx] ? i : inx);
 74     }
 75     // cout << "inx = " << inx << endl;
 76     int Min = cp[inx];
 77     vector<int > ans(n);
 78     for(int i = inx; i >= 0; --i){
 79         Min = min(Min, cp[i]);
 80         ans[i] = Min;
 81     }
 82     Min = cp[inx];
 83     for(int i = inx + 1; i < n; ++i){
 84         Min = min(Min, cp[i]);
 85         ans[i] = Min;
 86     }
 87     for(auto x : ans) cout << x << " ";
 88     cout << endl;
 89  
 90 }
 91  
 92 int main(){
 93     
 94     ios::sync_with_stdio(false);
 95     cin.tie(0);
 96     cout.tie(0);
 97     solve();
 98     
 99     return 0;
100 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄