Kimi LeetCode 3748. 统计稳定子数组的数目 Rust实现

以下是 LeetCode 3748「统计稳定子数组的数目」的 Rust 实现核心思路与 Java 版一致将数组划分为最长非降序段利用前缀和 二分查找处理查询。Rust 代码rustimpl Solution {pub fn count_stable_subarrays(nums: Veci32, queries: VecVeci32) - Veci64 {let n nums.len();// seg[i] 第 i 个非降序段的起始下标let mut seg: Vecusize Vec::new();// s[i] 前 i 个完整段中稳定子数组的总数前缀和let mut s: Veci64 Vec::new();s.push(0);let mut l 0;for r in 0..n {// 遇到下降nums[r] nums[r1]或到达末尾结束当前段if r n - 1 || nums[r] nums[r 1] {seg.push(l);let k (r - l 1) as i64;s.push(s.last().unwrap() k * (k 1) / 2);l r 1;}}let mut ans Vec::with_capacity(queries.len());for q in queries {let left q[0] as usize;let right q[1] as usize;// 找到第一个起始位置 left 的段即 left 所在段的下一个段let i seg.partition_point(|x| x left);// 找到第一个起始位置 right 的段再减 1 得到 right 所在段let j seg.partition_point(|x| x right).saturating_sub(1);if i j {// [left, right] 完全落在同一段内let k (right - left 1) as i64;ans.push(k * (k 1) / 2);} else {// 左端不完整段长度let a (seg[i] - left) as i64;// 右端不完整段长度let b (right - seg[j] 1) as i64;let res a * (a 1) / 2 // 左端贡献 s[j] - s[i] // 中间完整段贡献 b * (b 1) / 2; // 右端贡献ans.push(res);}}ans}}---关键点说明要点 说明划分段 遍历数组当 nums[r] nums[r1] 时切分保证每段内部非降序前缀和 s s[i] 表示前 i 个完整段的稳定子数组总数partition_point Rust 标准库提供的二分查找返回第一个不满足条件的下标等价于 upper_bound同一段内 若 i j直接用公式 k*(k1)/2跨段 左不完整段 中间完整段前缀和差 右不完整段时间复杂度 O((n q) log n)空间复杂度 O(n)。