【非零段划分 / 2】

题目

思路

第一种思路：按照表面题意，枚举p，处理数组后进行计数： 复杂度 ∈ O ( n ⋅ m ) 复杂度 \in O(n \cdot m) 复杂度∈O(n⋅m)

第二种思路：把数组看成一个二维的山形图，先将相邻的水平线段转化成点（对数组unique），再对每个子结构进行考虑 复杂度 ∈ O (    m i n ( n , m )    ) 复杂度 \in O(\;min(n, m)\;) 复杂度∈O(min(n,m))

具体思路：

1. 先unique，把相邻相等的元素去重
2. 分为三种子结构，考虑水面暴露其顶点后，其对非零段数量的贡献，记录在cnt[ ]数组中
   2.1. A形结构，只要“水面”暴露出顶点开始，对非零段数量的贡献为+1
   2.2. V形结构，只要“水面”暴露出顶点开始，对非零段数量的贡献为-1 把原本分离的两段合并了
   2.3 / \ 形结构，我们把中间点看作“顶点”，暴露顶点前后贡献不变
3. 遍历 p    f o r    [ M − 1 , 1 ] p \; for \;[M-1, 1] pfor[M−1,1] 模拟水面降低，维护一个 s u m sum sum 作为计数器

TLE代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int main()
{
    int n;
    cin >> n;
    int amax = 0;
    for(int i = 1; i <= n; i++) cin >> a[i], amax = max(amax, a[i]);
    
    int ans = 0;
    for(int p = 1; p <= amax; p++)
    {
        int cnt = 0; int last = 0;
        for(int i = 1; i <= n; i++)
        {
            int x = a[i];
            if(a[i] < p) x = 0;
            if(x && !last) cnt++;
            last = x;
        }
        ans = max(ans, cnt);
    }
    
    cout << ans;
    return 0;
}

正确代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10, M = 1e4+10;
int cnt[M], a[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    n = unique(a+1, a+n+1) - (a+1);
    a[0] = 0, a[n+1] = 0;
    for(int i = 1; i <= n; i++)
    {
        int x = a[i-1], y = a[i], z = a[i+1];
        if(x < y && z < y) cnt[y]++;
        if(x > y && z > y) cnt[y]--;
    }
    int ans = 0; int sum = 0;
    for(int i =  M - 1; i >= 1; i--)
    {
        sum += cnt[i];
        ans = max(ans, sum);
    }
    
    cout << ans;
    return 0;
}