What is the primary algorithmic pattern for solving 'Count the Number of Incremovable Subarrays II'?

The problem is typically solved using binary search over the valid answer space, combined with two-pointer techniques to validate subarrays.

How do I know when a subarray is incremovable?

A subarray is incremovable if removing it results in a strictly increasing sequence in the remaining array.

What edge cases should I consider when solving this problem?

Make sure to handle small arrays, large values, and situations where the entire array is considered a valid subarray.

Can I use dynamic programming to solve this problem?

While dynamic programming might be an option, the most efficient approach uses binary search and two pointers to track valid subarrays.

What is the time complexity of the optimal solution?

The optimal solution has a time complexity of O(n log n), where n is the length of the input array, due to the binary search combined with the two-pointer method.

#2972

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

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

给你一个下标从 0 开始的正整数数组 nums 。如果 nums 的一个子数组满足：移除这个子数组后剩余元素严格递增，那么我们称这个子数组为移除递增子数组。比方说， [5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组，因为移除该子数组后， [5, 3, 4, 6,…

数组双指针二分查找

题目描述

给你一个下标从 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⁵
1 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：双指针

根据题目描述，移除一个子数组后，剩余元素严格递增，那么存在以下几种情况：

剩余元素仅包含数组 $nums$ 的前缀（可以为空）；
剩余元素仅包含数组 $nums$ 的后缀；
剩余元素包含数组 $nums$ 的前缀和后缀。

其中第 $2$ 和第 $3$ 种情况可以合并为一种情况，即剩余元素包含数组 $nums$ 的后缀。即一共有以下两种情况：

剩余元素仅包含数组 $nums$ 的前缀（可以为空）；
剩余元素包含数组 $nums$ 的后缀。

我们先考虑第一种情况，即剩余元素仅包含数组 $nums$ 的前缀。我们可以用一个指针 $i$ 指向数组 $nums$ 的最长递增前缀的最后一个元素，即 $nums[0] \lt nums[1] \lt \cdots \lt nums[i]$ ，那么剩余元素的个数为 $n - i - 1$ ，其中 $n$ 为数组 $nums$ 的长度。因此，对于这种情况，要使得剩余元素严格递增，我们可以选择移除以下子数组：

$nums[i+1,...,n-1]$ ；
$nums[i,...,n-1]$ ；
$nums[i-1,...,n-1]$ ；
$nums[i-2,...,n-1]$ ；
$\cdots$ ；
$nums[0,...,n-1]$ 。

这一共有 $i + 2$ 种情况，因此对于这种情况，移除递增子数组的数目为 $i + 2$ 。

再考虑第二种情况，即剩余元素包含数组 $nums$ 的后缀。我们可以用一个指针 $j$ 指向数组 $nums$ 的递增后缀的第一个元素，我们在 $[n - 1,...,1]$ 的范围内枚举 $j$ 作为递增后缀的第一个元素，每一次，我们需要移动指针 $i$ 使得 $nums[i] \lt nums[j]$ ，那么移除递增子数组的数组增加 $i + 2$ 。当 $nums[j - 1] \ge nums[j]$ 时，我们停止枚举，因为此时后缀不是严格递增。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        i, n = 0, len(nums)
        while i + 1 < n and nums[i] < nums[i + 1]:
            i += 1
        if i == n - 1:
            return n * (n + 1) // 2
        ans = i + 2
        j = n - 1
        while j:
            while i >= 0 and nums[i] >= nums[j]:
                i -= 1
            ans += i + 2
            if nums[j - 1] >= nums[j]:
                break
            j -= 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate understands how to optimize subarray searches using binary search and pointers.
question_mark
The candidate effectively uses prefix arrays or similar techniques to track increasing sequences.
question_mark
The candidate can break down a problem requiring multiple steps into a clear, efficient approach.

warning

常见陷阱

外企场景

error
Misunderstanding the problem's constraints, leading to an inefficient solution.
error
Failing to optimize the subarray search, resulting in excessive time complexity.
error
Overlooking edge cases where subarrays are close to the entire array, requiring careful handling of boundaries.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increasing the size of the input array to test scalability.
arrow_right_alt
Handling arrays with larger values (e.g., elements in the range of 10^9).
arrow_right_alt
Exploring alternate approaches like dynamic programming or greedy algorithms for subarray validation.

help

常见问题

外企场景

继续练习

#2970 统计移除递增子数组的数目 I #2856 删除数对后的最小数组长度 #2824 统计和小于目标的下标对数目