CCF202109-2 非零段划分 学习笔记 python

CCF202109-2 非零段划分 学习笔记 python

1.索引数组（空间换时间）

数组L中有n个数，数字的范围大小为m，对于每个数字，遍历数组找到该数字，并且进行处理。对于该任务，显然时间复杂度是O（mn），但若提前遍历一遍数组，把每个数字i对应的下标进行储存，即数组idx[i]=[L中所有i所对应的下标]，则处理相同任务时间复杂度变为O(n+m)。

2 .一维岛屿情况

海面为0，岛屿为非零段，输入数组nums中的值代表当前下标位置的海拔高度。海平面从max(L)下降至1（海平面高度记为level），在海平面下降过程中，i处多了一个岛屿（非零段）当且仅当此时海平面高度<=i处海拔高度且[i-1],[i+1]处都为水（海拔小于海平面），i处减少了一个岛屿当且仅当此时此时海平面高度<=i处海拔高度且[i-1],[i+1]处都已经为岛屿。记数组island代表每个位置的目前状况(水或陆地)，即island[i]=0当且仅当nums[i]=level。

3.前缀和 presum（后缀和 postsum）

岛屿情况的改变量记录在islandchange数组中，islandchange[i]即为海平面高度level==i时，岛屿的增加量（增加为正，减少为负）。则显然，海平面每个高度对应的岛屿数量即为islandchange数组后缀和 sum(islandchange[i:])，遍历所得后缀和数组中最大值即为最大岛屿数量，即为题目所求。

4.python100分程序代码

# 数组前后补0
n = 2+int(input())
nums = [0]+list(map(int, input().split()))+[0]
maxnum = max(nums)

# idx[i]是一个列表，为数字i在nums中的index
idx = [[] for i in range(maxnum+1)]
for id, num in enumerate(nums):
    if num:
        idx[num].append(id)


# islandchange储存每次海平面变化带来的陆地数量变化值,
# 陆地数量的值就是非零段的数量
islandchange = [0]*(maxnum+1)
# 初始化岛屿数组，全都在水下,都初始化为0
island = [0]*len(nums)
# 海平面从maxnum降到1，海平面为i时对应状态即为：海拔i以及i以上陆地漏出来
for level in range(maxnum, 0, -1):
    # 本次露出水面的岛屿群的坐标储存在positions中
    positions = idx[level]
    # 由于初始化时nums两侧补0，u一定不为两端
    for u in positions:
        # 如果两侧为水，岛屿数量+1
        if island[u-1] == 0 and island[u+1] == 0:
            islandchange[level] += 1
        # 如果两侧为陆地岛屿数量-1
        elif island[u-1] == 1 and island[u+1] == 1:
            islandchange[level] -= 1
        # 否则岛屿数量不变化
        # 该点及时更新为陆地
        island[u] = 1

# 后序和
ans = 0
s = 0
for i in range(len(islandchange)-1, -1, -1):
    s += islandchange[i]
    ans = max(ans, s)
print(ans)