摘要
Title: 2014. 岛
Tag: 差分、思维、离散化
Memory Limit: 64 MB
Time Limit: 1000 ms

2014. 岛

题意

思路

模拟
先对岛进行相邻元素的去重，从低到高枚举岛
- 当此时岛与两边岛呈“凹”时，计数+1
- 当此时岛与两边岛呈“凸”时，计数-1
- 其余情况皆不变
  
  注意，相邻元素去重后，也会有元素是一样的，所以在更新答案时，应该等相邻元素不一样时更新
  
  比如下面这种情况
  
  有一个先+1后-1，应该同时发生，答案为2。但如果直接更新的话，答案会为3
差分

写的比较好的题解，Link
1. 为什么能用差分?
  考虑水平面不断升高的过程:
  - 第一种情况，在水平面处于 $[a[i - 1], a[i] - 1]$ 之间的时候，a[i]一定会是一个岛;
  - 第二种情况，在水平面低于a[i - 1]的时候，a[i - 1]和a[i]一起构成一个岛,我们此时把形成这个岛的功劳归给a[i - 1];
  - 第三种情况，水平面高于a[i]的时候，a[i]无法形成岛
  所以综上,a[i]对形成岛屿有贡献当且仅当水位是出于a[i - 1]到a[i] - 1之时(能贡献一个).
  所以我们只需要扫描所有的a[i],对每一个a[i]能贡献的区间加上1后,就能得到一个在不同的水位时的贡献图.自然而然的我们就能知道在什么水位的时候贡献最多(也就是岛屿最多).使用差分也仅仅是优化了这个对区间加1的过程.
2. 为什么只要使用a[i] > a[i-1]的时候才算入是a[i]的贡献? a[i] > a[i + 1]的时候呢?
  其实后者是多余的,因为一个地点能被称为岛屿也就说明其两侧水位必定小于岛屿的高度, 这是一个1对2的关系,考虑一侧就行,但是如果都考虑应该也行,只是感觉容易产生边界错误,并且贡献都成了两倍,结果要记得除二.
3. 其实就是某个岛存在是作用于某个区间的，对区间进行 $O(1)$ 的加减法，就可以用到差分

代码

注意 c++里的去重，是先将数组排好序，再用unique去重相邻元素，就是将数组中的数都去重了
但如果只用unique，只会去重相邻元素
python里的去重，list(set(xs))，直接将数组中的数都去重了
这里需要的只是去重相邻元素! 故不能用list(set(xs))

'''
Author: NEFU AB-IN
Date: 2022-02-12 17:45:15
FilePath: \ACM\Acwing\2014.py
LastEditTime: 2022-02-13 11:06:41
'''

xs = []  #原数组去重
a = []  #排序数组

if __name__ == "__main__":
    n = int(input())
    for i in range(n):
        x = int(input())
        xs.append(x)

    xs = [xs[i] for i in range(n) if i == 0 or xs[i - 1] != xs[i]]  #去重相邻元素
    xs = [0, *xs, 0]
    a = [[xs[i], i] for i in range(1, len(xs) - 1)]
    a.sort()  #所以说a排完序之后，可能还会有相同的数相邻（是原数组里隔开的两个相同的数）

    # 注意 c++里的去重，是先将数组排好序，再用unique去重相邻元素，就是将数组中的数都去重了
    # 但如果只用unique，只会去重相邻元素
    # python里的去重，list(set(xs))，直接将数组中的数都去重了
    # 这里需要的只是去重相邻元素! 故不能用list(set(xs))

    res, cnt = 1, 1
    for i in range(len(a) - 1):
        id = a[i][1]
        if xs[id] > xs[id + 1] and xs[id] > xs[id - 1]:
            cnt -= 1
        if xs[id] < xs[id + 1] and xs[id] < xs[id - 1]:
            cnt += 1

        if a[i][0] != a[i + 1][0]:  #相同时不更新，要等到不相同时才更新
            res = max(res, cnt)

    print(res)

差分

'''
Author: NEFU AB-IN
Date: 2022-02-15 15:38:39
FilePath: \ACM\Acwing\2014.1.py
LastEditTime: 2022-02-15 15:43:20
'''
from collections import Counter

N = int(1e5 + 20)
a = [0] * N
b = Counter()

if __name__ == "__main__":
    n = int(input())
    for i in range(1, n + 1):
        a[i] = int(input())
        if a[i] > a[i - 1]:
            b[a[i - 1]] += 1
            b[a[i] - 1 + 1] -= 1
    cnt, res = 0, 0
    for x in sorted(b.keys()):
        cnt += b[x]
        res = max(res, cnt)
    print(res)