3578. 计数划分，使最大最小差不超过 K

Source: Dev.to

问题

给定一个整数数组 nums 和一个整数 k。将 nums 划分为一个或多个 非空 连续子段，使得每个子段的 最大值 与 最小值 之差 不超过 k。

返回满足该条件的划分方式总数。

由于答案可能很大，请返回 模 10⁹ + 7 的结果。

示例

示例 1

Input:  nums = [9,4,1,3,7], k = 4
Output: 6

合法的划分（max‑min ≤ 4）：

• [[9], [4], [1], [3], [7]]
• [[9], [4], [1], [3,7]]
• [[9], [4], [1,3], [7]]
• [[9], [4,1], [3], [7]]
• [[9], [4,1], [3,7]]
• [[9], [4,1,3], [7]]

示例 2

Input:  nums = [3,3,4], k = 0
Output: 2

合法的划分：

• [[3], [3], [4]]
• [[3,3], [4]]

约束

• 2 ≤ nums.length ≤ 5·10⁴
• 1 ≤ nums[i] ≤ 10⁹
• 0 ≤ k ≤ 10⁹

提示

• 使用动态规划。
• 设 dp[i] 为以索引 i 结尾的最后一个子段的划分方式数。
• 结合滑动窗口和两个单调双端队列可以维护当前窗口的最小值和最大值。

解题思路

我们需要统计所有满足 max(segment) - min(segment) ≤ k 的划分方式。

动态规划

定义 dp[i] 为前缀 nums[0…i] 的合法划分数（最后一个子段以 i 结束）。
若子段 [j, i] 合法，则窗口 [j, i] 必须满足最大值‑最小值的条件。于是

[ dp[i] = \sum_{j=0}^{i} dp[j-1] \quad\text{对所有满足 }[j,i]\text{ 合法的 }j ]

其中基准情况 dp[-1] = 1（空前缀）。
利用前缀和数组 pref，上式可化为 dp[i] = pref[i] - pref[left-2]，其中 left 为能够构成以 i 结尾的合法子段的最左起始位置。

单调队列维护滑动窗口

维护窗口 [left, right]，right 从 0 遍历到 n‑1。
使用两个双端队列保存索引：

• minDeque：值递增，队首为当前窗口最小值。
• maxDeque：值递减，队首为当前窗口最大值。

向窗口加入 right 时，若新元素破坏单调性，则从队尾弹出元素直至恢复单调，然后将 right 入队。

如果 maxDeque.front() - minDeque.front() > k，则通过增大 left 并从队首移除离开窗口的索引来收缩窗口。

调整完毕后，left 即为以 right 结尾的合法子段的最小起始位置。

使用前缀和计算 dp

维护 pref[i] = (pref[i‑1] + dp[i]) mod M，其中 M = 1_000_000_007。

对每个 right = i：

dp[i] = pref[i-1] - (left > 0 ? pref[left-2] : 0)
dp[i] = (dp[i] + M) % M   // 保证非负
pref[i] = (pref[i-1] + dp[i]) % M

答案为 dp[n‑1]。

复杂度

• 时间复杂度： O(n) — 每个索引至多被推入/弹出队列一次。
• 空间复杂度： O(n) — 用于 dp、pref 以及两个队列。

参考实现（PHP）

setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO);
    $maxDeque->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO);

    $left = 0;

    for ($right = 0; $right isEmpty() && $nums[$minDeque->top()] >= $nums[$right]) {
            $minDeque->pop();
        }
        $minDeque->push($right);

        // maintain monotonic max deque
        while (!$maxDeque->isEmpty() && $nums[$maxDeque->top()] pop();
        }
        $maxDeque->push($right);

        // shrink window until condition satisfied
        while ($nums[$maxDeque->bottom()] - $nums[$minDeque->bottom()] > $k) {
            if ($minDeque->bottom() == $left) $minDeque->shift();
            if ($maxDeque->bottom() == $left) $maxDeque->shift();
            ++$left;
        }

        // compute dp[right]
        $total = $right > 0 ? $pref[$right - 1] : 0;
        $sub   = ($left > 0) ? $pref[$left - 2] : 0;
        $dp[$right] = ($total - $sub + $mod) % $mod;

        // update prefix sum
        $pref[$right] = ($total + $dp[$right]) % $mod;
    }

    return $dp[$n - 1];
}

// Test cases
echo countPartitions([9, 4, 1, 3, 7], 4) . PHP_EOL; // 6
echo countPartitions([3, 3, 4], 0) . PHP_EOL;       // 2
?>