算法不难，难在分析问题：双指针推进过程枚举所有答案

摘要: 经过分析，发现双指针可以解决问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，本文我们看一个困难的计数问题，也是出在某次周赛的最后一题。

仅从算法上看，本题只涉及一个双指针，谈不上困难。但难在分析问题的过程，这不是双指针的套路题，必须仔细分析满足条件的答案的特点，才能发现双指针的推进过程可以不重不漏地枚举出所有答案。

数组上的问题分析涉及到的对象不多，常见的比如逆序、圈、左向右最大值、上升、下降、游程、峰、谷、平原。对于陌生问题，可以优先从这些对象开始考虑。

题目

• 2972. 统计移除递增子数组的数目 II

给你一个下标从 0 开始的 正 整数数组 nums 。

如果 nums 的一个子数组满足：移除这个子数组后剩余元素 严格递增 ，那么我们称这个子数组为 移除递增 子数组。比方说，[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组，因为移除该子数组后，[5, 3, 4, 6, 7] 变为 [5, 6, 7] ，是严格递增的。

请你返回 nums 中 移除递增 子数组的总数目。

注意 ，剩余元素为空的数组也视为是递增的。

子数组 指的是一个数组中一段连续的元素序列。

提示：

1 <= nums.length <= 1e5
1 <= nums[i] <= 1e9

示例 1：
输入：nums = [1,2,3,4]
输出：10
解释：10 个移除递增子数组分别为：[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4] 和 [1,2,3,4]。移除任意一个子数组后，剩余元素都是递增的。注意，空数组不是移除递增子数组。

示例 2：
输入：nums = [6,5,7,8]
输出：7
解释：7 个移除递增子数组分别为：[5], [6], [5,7], [6,5], [5,7,8], [6,5,7] 和 [6,5,7,8] 。
nums 中只有这 7 个移除递增子数组。

示例 3：
输入：nums = [8,7,6,6]
输出：3
解释：3 个移除递增子数组分别为：[8,7,6], [7,6,6] 和 [8,7,6,6] 。注意 [8,7] 不是移除递增子数组因为移除 [8,7] 后 nums 变为 [6,6] ，它不是严格递增的。

题解

记数组为 $A$，由于删除的是一个子数组，因此不妨将剩下的部分记为左半部分 $[0, i]$、右半部分 $[j, n-1]$。被删的部分为 $[i+1, j-1]$。

左半部分与右半部分拼接起来后需要严格单调递增，因此 $[0, i]$ 和 $[j, n-1]$ 这两段需要严格单调递增，并且 $A[i] < A[j]$。

有了以上性质，会有一个感觉：假设被删子数组的左端点固定了，那么满足要求的右端点的取值范围大小可以直接计算出来，而不用一个一个地枚举去看是否满足要求。

• 由于 $A[0],\cdots,A[i]$ 的部分必须严格单调递增，因此假设 $A$ 从 $A[0]$ 开始先单调递增，到某一点 $A[l]$ 就不单调递增了，即 $A[l] \geq A[l + 1]$，那么 $A[l + 1]$ 无论如何也不可能出现在删除子数组后剩下的左半部分中，也就是说，$i$ 的范围只能是 $[0, l]$，对应的被删子数组左端点为 $i + 1 \in [1, l+1]$。

• 类似地，由于 $A[j],\cdots,A[n-1]$ 的部分必须严格单调递增，因此假设 $A$ 从 $A[n-1]$ 开始，反向地先单调递增，到某一点 $A[r]$ 就不满足了，即 $A[r-1] \geq A[r]$，那么 $A[r-1]$ 无论如何也不可能出现在删除子数组后剩下的右半部分中，也就是说 $j$ 的范围只能是 $[r, n-1]$，对应的被删子数组的右端点为 $j-1 \in [r-1,n-2]$。

以上分析如下图：

算法：双指针

基于以上分析，我们俩就可以有了大致思路。

从小到大枚举 $i=1,2,\cdots,l$，在严格递增的 $A[r],\cdots,A[n-1]$ 中找到第一个比 $A[i]$ 大的元素，记其为 $A[j]$，那么当 $A[i+1]$ 作为被删子数组的左端点时，$A[j-1]$ 可以作为被删子数组的右端点，$A[j],\cdots,A[n-1]$ 自然也可以作为被删子数组的右端点，共 $1 + n - j$ 种，将 $1 + n - j$ 累加到答案里即可。

问题在于如何高效找到上述的 $j$，这里有一个最重要的性质。由于 $A[0],\cdots,A[l]$ 和 $A[r],\cdots,A[n-1]$ 均严格递增，因此当 $i$ 逐渐自增的时候，对应的 $j$ 一定不会减小。因此可以用类似于双串单向双指针的方式维护 $i, j$。

此外还需要注意一下特殊情况，有两个方面：

• 整个数组都是严格单调递增的（数组仅一个元素也算这种情况），那么按上述逻辑得到的 $l$ 为 $n-1$。此时所有可能的非空子数组都是答案，因此直接返回 $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ 即可。
• 整个数组并不严格单调，此时会有 $0 \leq i < j \leq n-1$，按上述逻辑，我们考虑了被删子数组左端点为 $1, 2, \cdots, l + 1$。左端点为 $0$ 的情况需要单独考虑，此时 $r-1,r,\cdots,n-1$ 均可以作为右端点。因此初始时直接把 $1 + n - r$ 加到答案，然后再枚举 $i=1,2,\cdots,l$ 即可。

代码 (Python)

class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)
        l = 0
        while l + 1 < n and nums[l] < nums[l + 1]:
            l += 1
        if l == n - 1:
            return n * (n + 1) // 2
        r = n - 1
        while l < r - 1 and nums[r - 1] < nums[r]:
            r -= 1
        print(l, r)
        ans = 1 + n - r # 以 0 开始的子数组个数
        print(ans)
        i = 0
        j = r
        while i <= l:
            while j < n and nums[i] >= nums[j]:
                j += 1
            # 以 i + 1 开头的子数组个数
            ans += 1 + n - j
            i += 1
        return ans

---