Leetcode-2972题解

leetcode 2972 题解

leetcode 2970 的升级版

题目

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

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

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

注意，剩余元素为空的数组也视为是递增的, 子数组 指的是一个数组中一段连续的元素序列。

示例 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] ，它不是严格递增的。

提示：
1 <= nums.length <= $10^5$
1 <= nums[i] <= $10^9$

思路

双指针

本题的数据量非常大，直接枚举肯定超时。双指针解法理解起来比较容易，但在实现的过程中，可能会在 下标 上出现问题。

使用 [l,r] 表示 nums 中下标在 [l,r] 范围内的子数组。可以观察到，如果 [l,r] 是移除递增子数组，那么 [l-1,r] 也同样是移除递增子数组（证明：如果 [l,r] 是移除递增子数组，必有 [0,l-1] 和 [r+1,n-1] 是严格单调递增的，且 nums[l-1]<nums[r+1] ；对于 [l-1,r] ，必有 [0,l-2] 和 [r+1,n-1] 是严格单调递增的，且 nums[l-2]<num[l-1]<nums[r+1] ，故此推论成立）。由数学归纳法的思想可以得出，当 l<=r 时， [0,r], [1,r], ... , [l-1,r], [l,r] 都是移除递增子数组。

因此，对于某个固定的 r ，只需要找到最大的 l ，使得 [l,r] 为移除递增子数组，即可快速得到当前 r 的移除递增子数组的总数。

由上面的结论可以推出，下一步就是针对所有 r 找到对应的最大的 l 。首先针对 r=n-1 求出对应的 l ， n-1 这个下标对应的移除递增子数组的总数就是 l+(l<n) 。这里的下标比较难理解，举个例子说明一下。

数组：[1,2,2,3]，对于 r=3 ， l 应为 2 ，因为 [2,3] 是移除递增子数组， [3] 不是移除递增子数组， [2,2,3] 是移除递增子数组，但 l 并非最大值。对于 l=2, r=3 ，移除递增子数组有 [2,3],[2,2,3],[1,2,2,3] 共 3 个。
数组：[1,2,2,2]，对于 r=3 ， l 应为 3 ，因为 [2] 是移除递增子数组， [2,2] 是移除递增子数组，但 l 并非最大值。对于 l=3, r=3 ，移除递增子数组有 [2],[2,2],[2,2,2],[1,2,2,2] 共 4 个。

那么此时，这个 l 对应的就是数列中，除了移除递增子数组以外的最大值，即 nums[n-1] 。将指针 r 往前移动，假设 nums[n-2] 小于 nums[n-1] （若 nums[n-2] 大于 nums[n-1] ，则 n-2 右边已经不存在严格单调递增数列，此时已经没必要将 r 往前移动，因为移除单调递增子数列只会有 1 个），则 [0,n-2] 也存在移除递增子数列，且 nums[0,l-1] 一定是严格单调递增的。所以，对于 nums[n-2] 及其他数据，应该把指针 l 往左移动，直至 nums[n-2-1] （或 nums[r-1] ）小于 nums[l+1] 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int incremovableSubarrayCount(vector<int>& nums) {
        int n = nums.size(), count = 0, l = 1, r = nums.size() - 1;
        while (l < n && nums[l - 1] < nums[l])
            l++;
        count += l + (l < n);
        for (int i = n - 2; i >= 0; i--) {
            int templeft = l;
            while (l > 0 && nums[l - 1] >= nums[i + 1]) {
                l--;
            }
            count += l + (l <= i);
            if (nums[i] >= nums[i + 1]) {
                break;
            }
        }
        return count;
    }
};