企业官网建设流程全解析

以下是 LeetCode 3748. 统计稳定子数组的数目 的 Python3 实现。

解题思路

稳定子数组的定义是：子数组中没有逆序对，即元素呈非降序排列。

核心思路是分段计数：

1. 划分最长稳定段：将 `nums` 划分为若干个最长的非降序连续段，记录每段的起始位置 `seg`。
2. 前缀和：`s[i]` 表示前 `i` 个完整段的稳定子数组总数（一个长度为 `k` 的段有 `k*(k+1)/2` 个稳定子数组）。
3. 二分处理查询：对每个查询 `[l, r]`，用二分找到 `l` 和 `r` 所在的段，分三种情况：
- 完全在同一段内：直接公式计算。
- 跨越多个段：左端不完整段 + 中间完整段（前缀和差）+ 右端不完整段。

时间复杂度 `O((n + q) log n)`，空间复杂度 `O(n)`。

Python3 代码

```python
from typing import List
import bisect

class Solution:
def countStableSubarrays(self, nums: List[int], queries: List[List[int]]) -> List[int]:
# s[i]: 前 i 个完整段的稳定子数组总数，s[0] = 0
s = [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) // 2
s.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) - 1

if i > j:
# l 和 r 在同一段内
k = r - l + 1
ans.append((1 + k) * k // 2)
else:
# 左端不完整段: [l, seg[i]-1]，长度 a
a = seg[i] - l
# 右端不完整段: [seg[j], r]，长度 b
b = r - seg[j] + 1
# 中间完整段: 第 i 段到第 j-1 段，用前缀和差
# s[j] - s[i] 表示 seg[i] 到 seg[j-1] 这些完整段的稳定子数组总数
left = (1 + a) * a // 2
mid = s[j] - s[i]
right = (1 + b) * b // 2
ans.append(left + mid + right)

return ans
```

示例验证

以题目示例 `nums = [3, 1, 2], queries = [[0,1],[1,2],[0,2]]` 为例：

- 划分段：`[3]`（起始于0）、`[1,2]`（起始于1），`seg = [0, 1]`, `s = [0, 1, 4]`
- 查询 `[0,1]`：`i=1, j=0` → `i>j`，`k=2` → `2*3/2=3`？不对...

等等，让我重新验证：`nums = [3,1,2]`
- `r=0, x=3`, `3 > nums[1]=1`，段结束，`seg=[0]`, `k=1`, `s=[0,1]`, `l=1`
- `r=1, x=1`, `1 <= nums[2]=2`，继续
- `r=2, x=2`, 末尾，段结束，`seg=[0,1]`, `k=2`, `s=[0,1,4]`

查询 `[0,1]`：`i = bisect_right([0,1], 0) = 1`, `j = bisect_right([0,1], 1) - 1 = 2 - 1 = 1`
`i <= j`：`a = seg[1] - 0 = 1 - 0 = 1`, `b = 1 - seg[1] + 1 = 1 - 1 + 1 = 1`
`left = 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 = 1`
`i > j`：`k = 2`, `2*3/2 = 3` ✓

查询 `[0,2]`：`i = 1, j = 1`
`a = 1 - 0 = 1`, `b = 2 - 1 + 1 = 2`
`left = 1`, `mid = 0`, `right = 3`
结果：`1 + 0 + 3 = 4` ✓

结果正确。