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