核心思路

我们要找一段最长的连续坑，可以用 1 块木板（盖住连续 d 个坑） + 沙子（填剩下的坑） 的方式处理，且沙子用量 ≤ p。

关键观察：
对于任意区间 [i, j]，我们一定会用木板盖掉其中 连续 d 个坑且沙子需求总和最大 的那一段，这样剩下的沙子需求最小。

所以问题变成：
找到最长的区间 [L, R]，使得
区间总沙子需求 − 区间内长度 d 的最大子段和 ≤ p

解法

滑动窗口 + 单调队列

1. 预处理：

   • 计算前缀和，方便求任意区间和
   • 计算所有长度为 d 的连续子段的和（即每个位置开始的 d 个坑的沙子需求）

2. 单调队列：

   • 维护当前区间内 长度 d 的子段和的最大值
   • 队列按子段和递减，队首永远是当前窗口内最大值

3. 滑动窗口：

   • 固定左端点 i，尽量扩展右端点 j
   • 用单调队列快速得到 [i, j] 内长度 d 的最大子段和
   • 如果 区间和 − 最大d段和 > p 则停止扩展 j
   • 记录最大长度

算法流程

1. 左指针 i 从 1 到 n 遍历
2. 右指针 j 从 i+d−1 开始向右扩展
3. 每次 j 右移，更新单调队列（加入以 j−d+1 开头的 d 段）
4. 检查条件：sum[i..j] − maxDsegment ≤ p
   如果满足，继续扩展 j；否则停止，更新答案
5. 单调队列在左指针移动时弹出过时元素

复杂度

• 时间复杂度：O(n)
  每个元素进入和离开队列各一次，左右指针各遍历一次
• 空间复杂度：O(n)
  用于存储前缀和、d 段和、队列