Kimi k2.6 LeetCode 2972. 统计移除递增子数组的数目 II Python3实现
以下是 LeetCode 2972. 统计移除递增子数组的数目 II 的 Python3 实现，采用双指针思路。
核心思路
1. 找最长递增前缀：从左边开始找到最长的严格递增前缀，末尾索引为 `i`
2. 找最长递增后缀：从右边开始找到最长的严格递增后缀，起始索引为 `startIndex`
3. 双指针枚举：枚举左前缀的结束位置，用双指针找到右后缀中第一个大于左前缀末尾的位置，计算可移除的子数组数量
如果整个数组已经严格递增，则任意子数组都是移除递增的，答案为 `n * (n + 1) // 2`。
Python3 代码
```python
from bisect import bisect_right
from typing import List
class Solution:
def incremovableSubarrayCount(self, nums: List[int]) -> int:
n = len(nums)
# 找到最长递增前缀的末尾索引
i = 0
while i + 1 < n and nums[i] < nums[i + 1]:
i += 1
# 如果整个数组严格递增，任意子数组移除后都递增
if i == n - 1:
return n * (n + 1) // 2
# 找到最长递增后缀的起始索引
startIndex = n - 1
while startIndex > 0 and nums[startIndex - 1] < nums[startIndex]:
startIndex -= 1
# 情况1：移除子数组包含整个后缀 [startIndex..n-1]
# 左前缀可以是 [0..0], [0..1], ..., [0..i] 以及空（移除整个数组）
# 共 i + 2 种（空前缀 + i+1 种非空前缀）
ans = i + 2
# 双指针：枚举左前缀结束位置 j，找右后缀中第一个 > nums[j] 的位置
j = startIndex
for left_end in range(startIndex):
# 左前缀必须严格递增，遇到非递增则停止
if left_end > 0 and nums[left_end] <= nums[left_end - 1]:
break
# 移动右指针，找到第一个 > nums[left_end] 的位置
while j < n and nums[j] <= nums[left_end]:
j += 1
# 可移除的子数组为 [left_end+1 .. k]，其中 k 从 j-1 到 n-1
# 即移除子数组的右端点可以是 j-1, j, ..., n-1
# 共 n - j + 1 种
ans += n - j + 1
return ans
```
另一种实现（更简洁的双指针）
```python
from typing import List
class Solution:
def incremovableSubarrayCount(self, nums: List[int]) -> int:
n = len(nums)
# 找最长递增前缀末尾
i = 0
while i + 1 < n and nums[i] < nums[i + 1]:
i += 1
# 整个数组递增
if i == n - 1:
return n * (n + 1) // 2
# 找最长递增后缀起点
startIndex = n - 1
while startIndex > 0 and nums[startIndex - 1] < nums[startIndex]:
startIndex -= 1
ans = 0
j = startIndex
# left_end 从 -1 开始（表示空前缀）
for left_end in range(-1, startIndex):
if left_end >= 0:
# 左前缀必须严格递增
if left_end > 0 and nums[left_end] <= nums[left_end - 1]:
break
# 移动右指针
while j < n and nums[j] <= nums[left_end]:
j += 1
# 可移除子数组数量
ans += n - j + 1
return ans
```
关键点说明
要点 说明
递增前缀 `nums[0..i]` 是最长的严格递增前缀
递增后缀 `nums[startIndex..n-1]` 是最长的严格递增后缀
双指针 `left_end` 枚举左前缀结束位置，`j` 指向右后缀中第一个 `> nums[left_end]` 的位置
可移除子数组 对于固定的 `left_end`，移除子数组可以是 `[left_end+1 .. k]`，其中 `k ∈ [j-1, n-1]`，共 `n-j+1` 种
边界条件 `left_end = -1` 表示空前缀，即只保留右后缀
复杂度分析
- 时间复杂度：O(n)，双指针每个位置最多访问一次
- 空间复杂度：O(1)