从一道例题开始

有一片大海，大海中隐藏着若干陆地，当海平面下降的时候漏出的连续陆地会组成一个小岛，问题：当海平面处于多高的时候才能使漏出的小岛数量最多？数量是多少？

差分法解释

一个数组$A[1,2,3,4,5,6,7,8,9]$他的差分数组就是$A[i]-A[i-1]$，为方便计算我们给数组$A$头部插入一个0，变为$A[0,1,2,3,4,5,6,7,8,9]$，则其差分数组为$B[0,1,1,1,1,1,1,1,1,1]$(头部0也是单独插入的)，差分数组又一个很重要的性质,$\sum_0^nB[i]=A[n]$，即$B$的前缀和等于$A$的相应下表的值，这有什么用呢？例如我们想给$A[2:6]$区间+1，除了直接在$A$中循环，还可以把$B$更改为$[0,1,2,1,1,1,1,0,1,1]$,即$B[2]+1,B[7]-1$,然后在按照前缀和的形式加回去，也能算出来，这就是差分法，上题就是一个经典案例。

暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> nums = {6, 5, 7, 1, 4, 2, 4};
    nums.insert(nums.begin(), 0);
    nums.push_back(0);
    int max_value = *max_element(nums.begin(), nums.end());
    vector<int> levels(max_value + 1);//海平面
    for(int i = 1; i < nums.size() - 1; ++i)
    {
        if(nums[i] > nums[i - 1])
        {
            for(int j = nums[i - 1] + 1; j <= nums[i]; ++j)
            {
                levels[j]++;
            }
        }
    }
    cout << *max_element(levels.begin(), levels.end());
    return 0;
}

很明显，复杂度$O(n^2)$

差分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void add_diff(vector<int>& diff, int low, int high)
{
    diff[low]++;
    diff[high + 1]--;
}

int main()
{
    vector<int> nums = {6, 5, 7, 1, 4, 2, 4};
    nums.insert(nums.begin(), 0);
    nums.push_back(0);
    int max_value = *max_element(nums.begin(), nums.end());
    vector<int> diff(max_value + 1);//差分数组
    for(int i = 1; i < nums.size() - 1; ++i)
    {
        if(nums[i] > nums[i - 1])
        {
            add_diff(diff, nums[i - 1] + 1, nums[i]);
        }
    }
    int maxn = 0, pre = 0;
    for(int p = 1; p <= max_value; p++)
    {
        pre += diff[p];
        maxn = max(maxn, pre);
    }
    cout << maxn;
    return 0;
}

复杂度$O(n)$