岛

思路

首先，阅读题目，抽象出来问题的模型。这里有个十分重要的点，想通之后就会变得简单些

问题中说水位是连续上升的，但是仔细一想，只有水位达到某个山的高度时，题目的状态才会发生变化，当水位在其他位置时无论怎么变化对题目状态是没有丝毫影响的。所以，我们只需要考虑题目中所有出现过的高度就行了

然后，考虑问题的规模时，大致上可以使用$O(n)O(n)$或者$O(nlogn)O(nlogn)$的算法求解。我们可以考虑枚举一下所有高度。于是，对每一个高度，我们要考虑所有发生变化的山。如何做？我们可以在$O(N)O(N)$的时间里全部遍历一遍，但是这样就超时了。考虑到每次只有水位等于山的高度的山附近会发生变化，所以我们可以先按照山的高度排个序，然后从小到大枚举。

对于被水位淹没的对应高度的山，有四种情况

低中高、高中低、低高低、高低高

但是只有两种情况下问题的状态会发生变化。这样就解决了这个问题。枚举花费时间$O(N)O(N)$，排序花费时间$O(nlogn)O(nlogn)$，不会超时。

另外，还要注意几个问题

1. 需要把原数组h中相等且相邻的山去重，使用unique函数即可。
2. 边界情况，h数组下标从1开始，最后把边界全看成了平地
3. 当遇到排序需要记住数组下标时，可以使用pair<int,int>

代码

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N = 1e5 + 10;

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;//res记录最大的结果,cnt记录当前的岛屿数量
    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++;
        
        //如果有相同高度的山，需要把该高度的所有山淹没完再更新cnt
        if(q[i].first != q[i+1].first)
            res = max(res, cnt);
    }
    
    cout << res << endl;
    
    return 0;
}

unique的一个小细节