---
title: "岛"
created: 2025-11-28
tags:
  - 算法
---

# 岛

## 题目 [岛](https://www.acwing.com/problem/content/description/2016/)

![[image-8f43cbc8.png]]

## 思路分析

思路见上一题 [[非零段划分|非零段划分]]

唯一的不同在于 数据范围变得更大

使得我们无法使用数组存下 在整个差分数组更新每个点状态修改后对答案的影响

最后再把所有元素构造前缀和 把所有时间点的岛数算出来

那么就得把数据离散化成比较小的范围 能够放得下 让我们可以用差分

即舍去一些用不到的元素

对于第一二种做法（从水平线入手） 可以发现

我们要用到的是只是去掉相邻相同元素的那些点

我们确实做了去重 但是实际上对答案有影响的也只是他们

我们没必要对整个数组做差分→前缀和 （算所有时间点的岛域数 找最大）

没用到的点都是0 差分中 0不构成任何影响

那么就把所有要用到的岛离散化出来

排序一下 从小到大或者从大到小去取出 每轮累加一下和

实际上和 做前缀和后缀和是一样的（细品）

这样就变成了 算每次淹没/露出这些**关键时间点**的岛屿数

当然 有个注意的点就是 如果存在

![[image-ad3f4bd8.png]]

这样 处于同一水平面（不相邻所以不会被去重）的

他们处于同一个时刻 结果应该要在同一轮计算 而不能这一轮加了 下一轮减掉

（之前的前缀和方式是以时间为单位的 在该时间++ -- 最后再统一算 所以会平衡

而这里 是要每轮出答案 如果先加了 这个可能被当成最大的res保存了 显然有问题）

所以 我们在做的时候得进行一次判断 如果下一个点跟这一个点在同一水平位置

那我们这次就不更新答案

只有与下一个点不同时 才更新答案

对于第二种情况

跟我们平时做的离散化就更相似些了

我们本身就是在插入的时候进行差分操作

最后再把所有时间点求一次前缀和

但是现在这个for(1~10000）变成了1~$10^9$

不能这样做了

那么 可以直接把这些东西放在map里面 而不是一个数组里面

我们使用map来实现离散化 代替数组做差分

## 代码实现

**从下往上**

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int N=100010;
int n;
int h[N];
PII q[N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>h[i];
    n=unique(h+1,h+n+1)-(h+1);
    h[n + 1] = 0;
    for(int i=1;i<=n;i++)
        q[i]={h[i],i};
    sort(q+1,q+n+1);
    int res=1,cnt=1;
    for(int i=1;i<=n;i++){
        int k=q[i].second;
        if(h[k-1]<h[k] && h[k+1]<h[k])
            cnt--;
        else if(h[k-1]>h[k] && h[k+1]>h[k])
            cnt++;
        if(q[i].first!=q[i+1].first)
            res=max(res,cnt);
    }
    cout<<res<<endl;
    return 0;
}
```

**从上往下**

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int N=100010;
int n;
int h[N];
PII q[N];

bool cmp(pair<int, int>a, pair<int, int>b)
{
    return a.first>b.first;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>h[i];
    n=unique(h+1,h+n+1)-(h+1);
    h[n + 1] = 0;
    for(int i=1;i<=n;i++)
        q[i]={h[i],i};
    sort(q+1,q+n+1,cmp);

    int res=0,cnt=0;
    for(int i=1;i<=n;i++){
        int k=q[i].second;
        if(h[k-1]<h[k] && h[k+1]<h[k])
            cnt++;
        else if(h[k-1]>h[k] && h[k+1]>h[k])
            cnt--;
        if(q[i].first!=q[i+1].first)
            res=max(res,cnt);
    }
    cout<<res<<endl;
    return 0;
}
```

**从点入手 差分 map实现**

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 100010,M = 1e9+10;
int a[N];
map<int ,int >b;//用map代替数组 实现离散化的差分
int n;

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
        if(a[i]>a[i-1]){
            b[a[i-1]]++,b[a[i]]--;
        }
    }

    LL sum = 0 ,res = 0;
    for (auto i:b ){
        sum+=i.second;
        res = max(res,sum);
    }
    cout<<res<<endl;
}
```

**从点入手 差分 手写离散化**

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 100010,M = 1e9+10;
int a[N];
vector<int> alls;
int b[N];
int n;

int find(int x)
{
    int l=0,r=alls.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(alls[mid]>=x)
            r=mid;
        else
            l=mid+1;
    }
    return r;
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
        alls.push_back(a[i]);
    }

    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    for (int i = 1; i <= n; i ++ ){
        if(a[i]>a[i-1]){
            b[find(a[i-1])]++,b[find(a[i])]--;
        }
    }

    LL sum = 0 ,res = 0;
    for (auto i:b ){
        sum+=i;
        res = max(res,sum);
    }
    cout<<res<<endl;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[增减序列|增减序列]] 🏠 [[00-刷题理模型]] ➡️ [[差分|差分]]