一、题目题目描述近些年来我国防沙治沙取得显著成果。某沙漠新种植N棵胡杨编号1-N排成一排。一个月后有M棵胡杨未能成活。现可补种胡杨K棵请问如何补种只能补种不能新种可以得到最多的连续胡杨树输入描述N 总种植数量1 N 100000M 未成活胡杨数量M 个空格分隔的数按编号从小到大排列1 M NK 最多可以补种的数量0 K M输出描述最多的连续胡杨棵树示例1输入522 411234输出31说明补种到2或4结果一样最多的连续胡杨棵树都是3。示例2输入1032 4 711234输出61说明种第7棵树最多连续胡杨树棵数位65678910解题思路这道题目主要是考察如何通过补种胡杨树使得胡杨树形成【最长的连续序列】。示例解释示例1输入522 411234解释胡杨树总共有 5 棵编号分别是 1, 2, 3, 4, 5。未成活的胡杨树编号是 2 和 4。只能补种 1 棵树。选择补种位置可以补种编号为2的树得到序列 1, 2, 3最多连续 3 棵树。或者补种编号为4的树得到序列 3, 4, 5同样可以得到最多连续 3 棵树。因此输出结果为 3。示例2输入1032 4 711234解释胡杨树总共有 10 棵编号分别是 1 到 10。未成活的胡杨树编号是 2, 4, 7。只能补种 1 棵树。选择补种位置如果补种编号为7的树可以形成最长连续序列 5, 6, 7, 8, 9, 10连续的胡杨树棵数为 6。其他补种选择如2或4得到的最长连续胡杨树棵数较少。因此输出结果为 6。代码思路基本与下题一致最大连续1的个数 III参考题解https://leetcode.cn/problems/max-consecutive-ones-iii/solutions/608931/zui-da-lian-xu-1de-ge-shu-iii-by-leetcod-hw12/双指针解法容易理解二、代码# 读取胡杨树的总数Ntotalint(input())# 读取未成活胡杨树的数量Mdead_countint(input())# 读取未成活胡杨树的编号列表dead_listlist(map(int,input().split()))# 读取可以补种的胡杨树数量Ksupplement_countint(input())# 初始化数组所有树最初都是成活的0表示成活1表示未成活nums[0]*total# 根据输入将未成活的树的位置标记为1fornumindead_list:nums[num-1]1# 树的编号从1开始因此需要减1# 初始化滑动窗口的左右边界left0max_len0# 用于存储最大连续成活区域的长度sum_left0# 滑动窗口左边界的未成活树数量sum_right0# 滑动窗口右边界的未成活树数量# 遍历所有的树right代表滑动窗口的右边界forrightinrange(total):sum_rightnums[right]# 更新右边界的未成活树数量# 如果窗口内的未成活树数量大于可以补种的数量whilesum_right-sum_leftsupplement_count:sum_leftnums[left]# 缩小窗口左边界右移left1# 更新最大成活区域的长度max_lenmax(max_len,right-left1)# 输出最大连续成活区域的长度print(max_len)算法解析滑动窗口/双指针问题转化将 N 棵胡杨的成活状态成活0未成活1视为一个二进制数组nums。题目转化为在最多允许将 K 个 1 翻转为 0即补种 K 棵未成活树的条件下求数组中最长的连续 0 的子数组长度。滑动窗口维护left和right分别表示窗口的左右边界初始均为0。sum_right记录从数组开头到当前右边界right包含的未成活树即1的总数前缀和。sum_left记录从数组开头到左边界left之前即[0, left-1]区间的未成活树总数前缀和。这样窗口[left, right]内实际的未成活树数量为sum_right - sum_left。窗口扩张与收缩右指针right每次向右移动一位并更新sum_right。当窗口内未成活树数量(sum_right - sum_left)超过可补种数量K时说明窗口内需要补种的树太多了超过了限额此时需要收缩左边界left直到条件再次满足即移出一些未成活的树减少需要补种的数量。收缩时sum_left会累加被移出窗口的树的状态nums[left]。更新答案在每一步有效的窗口即窗口内未成活树数量 ≤ K中计算窗口长度right - left 1并更新全局最大值max_len。结果最终的max_len即为通过补种最多 K 棵树能获得的最长连续成活胡杨序列的长度。该算法时间复杂度为 O(N)空间复杂度为 O(N)用于存储状态数组可以高效处理 N 最大为 100000 的数据规模。说明