补种植胡杨树

题目描述

近些年来，我国防沙治沙取得显著成果。某沙漠新种植N棵胡杨（编号1-N），排成一排。

一个月后，有M棵胡杨未能成活。

现可补种胡杨K棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？

输入描述

N 总种植数量，1 <= N <= 100000

M 未成活胡杨数量，M 个空格分隔的数，按编号从小到大排列，1 <= M <= N

K 最多可以补种的数量，0 <= K <= M

输出描述

最多的连续胡杨棵树

示例1

输入：
5
2
2 4
1

输出：
3

示例2

输入：
10
3
2 4 7
1

输出：
6

题解

这道题目属于**滑动窗口（双指针）**类型的算法题。通过维护一个窗口来寻找满足特定条件的最优解，适用于需要在连续子数组或子序列中寻找最优解的场景。

解题思路

1. 问题分析：
   • 有一排胡杨树，其中某些位置（dead数组）的树未成活。
   • 可以补种最多 K 棵胡杨，补种的位置必须是未成活的位置（即 dead 数组中的位置）。
   • 目标是补种后，连续的成活胡杨树的最大数量。
2. 关键观察：
   • 补种的 K 棵胡杨一定是连续的（因为这样能最大化连续成活的数量）。
   • 问题转化为：在 dead 数组中找到长度为 K 的窗口，使得窗口左右边界外的成活胡杨树最多。
3. 滑动窗口：
   • 将 dead 数组的首尾添加哨兵元素（0 和 N+1），方便处理边界条件。
   • 用滑动窗口遍历 dead 数组，窗口大小为 K+1（因为补种 K 棵可以覆盖 K 个间隔）。
   • 计算窗口左右边界之外的成活胡杨树数量：dead[r] - dead[l] - 1。
4. 结果更新：
   • 每次滑动窗口时，更新最大连续成活数量 ans。

复杂度分析

• 时间复杂度：O(M)，其中 M 是未成活树的数量。滑动窗口只需遍历 dead 数组一次。
• 空间复杂度：O(M)，存储 dead 数组的空间。

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, M, K;
    cin >> N >> M;
    vector<int> dead(M + 2); 
    dead[0] = 0; // 添加哨兵
    for (int i = 1; i <= M; i++) {
        cin >> dead[i];
    }
    dead[M + 1] = N + 1; // 添加哨兵
    cin >> K;

    int ans = 0;
    for (int l = 0, r = K + 1; r < dead.size(); l++, r++) {
        ans = max(ans, dead[r] - dead[l] - 1);
    }
    cout << ans << endl;

    return 0;
}

什么是哨兵元素？

哨兵元素（Sentinel）是一种编程技巧，指在数据结构（如数组、链表等）中人为添加的特殊标记值，用于简化边界条件的处理，避免复杂的条件判断，提升代码的简洁性和运行效率。

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁 立即订阅。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏