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

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

题目描述：

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

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

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

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

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

数据范围：

$1\le nums.len \le 10^5, 1\le nums[i] \le 10^9$

题解：

首先需要发现一个特点。如果移出子数组之后剩余元素严格递增，那么剩余的肯定是一个前缀加后缀的形式，并且前缀是严格递增，后缀是严格递增，前缀的最后一个元素是严格小于后缀的第一个元素。

可以先单独处理出来最长的严格上升前缀 $[0, left]$ 和最长的严格上升后缀 $[right, n - 1]$ 。

如果只存在一个前缀或后缀，或前后缀一样，直接返回 $n(n + 1)/2$
针对前缀后缀不交叉的情况，假设删除 $[l, r]$ 则 $l \le left + 1, r \ge right - 1$

注意 $l$ 是可以达到 $left + 1$ 的，这时将会完全保留前缀，然后将后面的删除。

而且 $r$ 也是可以达到 $right - 1$ 的，这时将完全保留后缀，然后将前面的删除。

可以使用同向双指针，将 $l = 0, r = right - 1$ 开始移动，保证 $nums[l - 1] \lt nums[r + 1]$ 。

代码：

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    long long incremovableSubarrayCount(vector<int> &nums)
    {
        int n = nums.size();
        int left = 0, right = n - 1;
        while (left + 1 < n && nums[left] < nums[left + 1])
            left++;
        if (left == n - 1)
            return n * (n + 1) / 2;
        while (right - 1 >= 0 && nums[right] > nums[right - 1])
            --right;
        int l = 0, r = right;
        long long ans = 0;
        // 假设删除 [l, r - 1]
        while (l <= left + 1)
        {
            if (l == 0)
            {
                ans += n - r + 1;
                ++l;
                continue;
            }
            while (r < n && nums[r] <= nums[l - 1])
                ++r;
            ans += n - r + 1;
            ++l;
        }
        return ans;
    }
};