↓Skip to main content
  1. Posts/

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

·1 min·
Table of Contents

LeetCode-2972 统计移除递增子数组的数目 II #

Solution 1 #

移除一段递增子数组后, 剩余数组应当由一段严格递增前缀与一段严格递增后缀组成. 我们可以找出原数组的最长递增前缀 $nums[0: p + 1]$ 与最长递增后缀 $nums[q: ]$ . 需要注意的是题目不允许移除空的子数组, 首先特判 $p == n - 1$ 的情况. 一般情况下, 对于后缀 $nums[j: ]$ (要求 $j > 0$ 以满足移除子数组非空; 同时后缀也可以被完全移除, 需要特别计算), 寻找 $\argmax_i nums[i] < nums[j]$ , 此时, 移除 $nums[i + 1: j], nums[i: j], \cdots, nums[0:j]$ 都满足要求, 共 $i_j + 2$ 个. 由于前缀是严格递增的, 在减小 $j$ 时, 不断减小 $i$ 寻找可行解即可, 因此使用双指针进行统计. 代码如下:

class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)
        p, q = 0, n - 1
        for i in range(n - 1):
            if nums[i + 1] > nums[i]:
                p += 1
            else:
                break

        # 不能移除空的子数组 特判
        if p == n - 1:
            return n * (n + 1) // 2

        for i in range(n - 1, 0, -1):
            if nums[i - 1] < nums[i]:
                q -= 1
            else:
                break

        ans = p + 2 # 后缀全部被移除的情况

        for i in range(n - 1, max(q - 1, 0), -1):
            # 移除 nums[p + 1: i], nums[p: i], ..., nums[0: i]
            while p >= 0 and nums[p] >= nums[i]:
                p -= 1
            ans += p + 2
        return ans