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

以下是 LeetCode 3748. 统计稳定子数组的数目 的 Python3 实现。解题思路稳定子数组的定义是子数组中没有逆序对即元素呈非降序排列。核心思路是分段计数1. 划分最长稳定段将 nums 划分为若干个最长的非降序连续段记录每段的起始位置 seg。2. 前缀和s[i] 表示前 i 个完整段的稳定子数组总数一个长度为 k 的段有 k*(k1)/2 个稳定子数组。3. 二分处理查询对每个查询 [l, r]用二分找到 l 和 r 所在的段分三种情况- 完全在同一段内直接公式计算。- 跨越多个段左端不完整段 中间完整段前缀和差 右端不完整段。时间复杂度 O((n q) log n)空间复杂度 O(n)。Python3 代码pythonfrom typing import Listimport bisectclass Solution:def countStableSubarrays(self, nums: List[int], queries: List[List[int]]) - List[int]:# s[i]: 前 i 个完整段的稳定子数组总数s[0] 0s [0]# seg: 每个最长非降序段的起始位置seg []l, n 0, len(nums)# 划分最长稳定段for r, x in enumerate(nums):# 段结束条件到达末尾或当前元素 下一个元素出现降序if r n - 1 or x nums[r 1]:seg.append(l)k r - l 1 # 段长度# 长度为 k 的段稳定子数组个数 k * (k 1) // 2s.append(s[-1] (1 k) * k // 2)l r 1 # 下一段的起始位置ans []for l, r in queries:# i: 第一个起始位置 l 的段的索引即 l 所在段的下一段i bisect.bisect_right(seg, l)# j: 最后一个起始位置 r 的段的索引即 r 所在段j bisect.bisect_right(seg, r) - 1if i j:# l 和 r 在同一段内k r - l 1ans.append((1 k) * k // 2)else:# 左端不完整段: [l, seg[i]-1]长度 aa seg[i] - l# 右端不完整段: [seg[j], r]长度 bb r - seg[j] 1# 中间完整段: 第 i 段到第 j-1 段用前缀和差# s[j] - s[i] 表示 seg[i] 到 seg[j-1] 这些完整段的稳定子数组总数left (1 a) * a // 2mid s[j] - s[i]right (1 b) * b // 2ans.append(left mid right)return ans示例验证以题目示例 nums [3, 1, 2], queries [[0,1],[1,2],[0,2]] 为例- 划分段[3]起始于0、[1,2]起始于1seg [0, 1], s [0, 1, 4]- 查询 [0,1]i1, j0 → ijk2 → 2*3/23不对...等等让我重新验证nums [3,1,2]- r0, x3, 3 nums[1]1段结束seg[0], k1, s[0,1], l1- r1, x1, 1 nums[2]2继续- r2, x2, 末尾段结束seg[0,1], k2, s[0,1,4]查询 [0,1]i bisect_right([0,1], 0) 1, j bisect_right([0,1], 1) - 1 2 - 1 1i ja seg[1] - 0 1 - 0 1, b 1 - seg[1] 1 1 - 1 1 1left 1, mid s[1] - s[1] 0, right 1结果1 0 1 2 ✓查询 [1,2]i bisect_right([0,1], 1) 2, j bisect_right([0,1], 2) - 1 2 - 1 1i jk 2, 2*3/2 3 ✓查询 [0,2]i 1, j 1a 1 - 0 1, b 2 - 1 1 2left 1, mid 0, right 3结果1 0 3 4 ✓结果正确。