题目描述

难度分:$901$

输入$n(1 \leq n \leq 2 \times 10^5)$和一个$1$~$n$的排列$a$。下标从$1$开始。

有$n$幢楼房，高度从左到右记录在$a$中。定义$f(i)$表示$j$的个数，满足$i \lt j \leq n$且在$[i+1,j-1]$中没有比$j$高的楼房。

输出$f(1),f(2),…,f(n)$。

输入样例$1$

5
2 1 4 3 5

输出样例$1$

3 2 2 1 0

输入样例$2$

4
1 2 3 4

输出样例$2$

3 2 1 0

输入样例$3$

10
1 9 6 5 2 7 10 4 8 3

输出样例$3$

2 3 3 3 2 1 2 1 1 0

算法

动态规划+单调栈

乍一看感觉是$LIS$问题，$f(i)$应该是$dp[i+1]$，其中$dp[i+1]$表示以$a[i+1]$开头的最长不递减子序列的长度。但是发现一个问题，如果数组为3 1 5 2 4 6，要求$a[1]$的答案，$dp[2]=4$，可是$a[2]$开头的最长不递减子序列是1 2 4 6，但是原数组中$1$和$2$之间有一个比$2$大的$5$，这是不合法的。因此，对于每个$i$，它的转移来源应该是$j \gt i$，且满足$a[j] \geq a[i]$的最小$j$，这样才能保证$(i,j)$之间不会有$\gt a[j]$的数。

因此，倒序遍历数组$a$计算$dp$数组，用单调栈维护每个$i$的转移来源$j$，状态转移方程其实就是$dp[i]=dp[j]+1$。

复杂度分析

时间复杂度

倒序遍历一遍$a$数组就可以求得$dp$数组，在这个过程中还需要用单调栈维护信息，时间复杂度为$O(n)$。

空间复杂度

除了输入的$a$数组，空间消耗主要在于DP数组$dp$，以及单调栈。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int n, a[N], dp[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    dp[n + 1] = 0;
    stack<int> stk;
    for(int i = n; i >= 1; i--) {
        while(stk.size() && a[stk.top()] < a[i]) {
            stk.pop();
        }
        if(stk.size()) {
            dp[i] = dp[stk.top()] + 1;
        }else {
            dp[i] = 1;
        }
        stk.push(i);
    }
    for(int i = 1; i <= n; i++) {
        printf("%d ", dp[i + 1]);
    }
    return 0;
}