N幢楼排成一行,第i号楼的高度为H[i]。对于每幢楼,右边有多少幢楼满足两楼之间的楼高都不超过右侧楼高?
1<=N<=2E5, 1<=H[i]<=N, H[i]!=Hj
分析:单调栈求出各幢楼左边最近的比它高的楼,对于j号楼,假设它左边最近的比它高的楼号为i,那么j对区间[i,j-1]中每个下标都有1的贡献,可以用差分来维护。
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int N;
std::cin >> N;
std::vector<int> H(N + 2);
for (int i = 1; i <= N; i++) {
std::cin >> H[i];
}
std::vector<int> L(N + 2), s;
for (int i = 1; i <= N; i++) {
while (!s.empty() && H[s.back()] <= H[i]) {
s.pop_back();
}
L[i] = s.empty() ? 0 : s.back();
s.push_back(i);
}
std::vector<int> A(N + 2);
for (int i = 1; i <= N; i++) {
A[L[i]] += 1;
A[i] -= 1;
}
std::partial_sum(A.begin(), A.end(), A.begin());
for (int i = 1; i <= N; i++) {
std::cout << A[i] << " \n"[i == N];
}
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int t = 1;
while (t--) solve();
return 0;
}
标签:std,Buildings,int,abc372D,long,号楼
From: https://www.cnblogs.com/chenfy27/p/18450338