统计移除递增子数组的数目 II
难度:
标签:
题目描述
You are given a 0-indexed array of positive integers nums.
A subarray of nums is called incremovable if nums becomes strictly increasing on removing the subarray. For example, the subarray [3, 4] is an incremovable subarray of [5, 3, 4, 6, 7] because removing this subarray changes the array [5, 3, 4, 6, 7] to [5, 6, 7] which is strictly increasing.
Return the total number of incremovable subarrays of nums.
Note that an empty array is considered strictly increasing.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,2,3,4] Output: 10 Explanation: The 10 incremovable subarrays are: [1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4], and [1,2,3,4], because on removing any one of these subarrays nums becomes strictly increasing. Note that you cannot select an empty subarray.
Example 2:
Input: nums = [6,5,7,8] Output: 7 Explanation: The 7 incremovable subarrays are: [5], [6], [5,7], [6,5], [5,7,8], [6,5,7] and [6,5,7,8]. It can be shown that there are only 7 incremovable subarrays in nums.
Example 3:
Input: nums = [8,7,6,6] Output: 3 Explanation: The 3 incremovable subarrays are: [8,7,6], [7,6,6], and [8,7,6,6]. Note that [8,7] is not an incremovable subarray because after removing [8,7] nums becomes [6,6], which is sorted in ascending order but not strictly increasing.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109
代码结果
运行时间: 58 ms, 内存: 30.3 MB
/*
* Solution approach for the problem using Java Stream:
* 1. Generate all possible subarrays of the given array.
* 2. For each subarray, remove it from the array and check if the remaining array is strictly increasing.
* 3. Count the subarrays that satisfy the condition.
*/
import java.util.stream.IntStream;
public class Solution {
public long countRemovalIncreasingSubarrays(int[] nums) {
int n = nums.length;
return IntStream.range(0, n)
.boxed()
.flatMap(start -> IntStream.range(start, n).mapToObj(end -> new int[]{start, end}))
.filter(range -> isRemainingArrayIncreasing(nums, range[0], range[1]))
.count();
}
private boolean isRemainingArrayIncreasing(int[] nums, int start, int end) {
int n = nums.length;
int prev = -1;
for (int i = 0; i < n; i++) {
if (i >= start && i <= end) continue;
if (prev != -1 && nums[i] <= prev) return false;
prev = nums[i];
}
return true;
}
}
解释
方法:
这道题的解题思路主要是以移除子数组的左端点为基础进行枚举，并尝试找到每个可能的右端点。算法首先找到从数组末尾开始的第一个非递增的位置，这有助于快速排除那些不能作为子数组右端点的位置。之后，算法从数组开始处逐个尝试作为子数组的左端点，并寻找可能的右端点，从而确保移除后的数组是递增的。如果左端点和右端点之间的元素是递增的，则继续移动左端点。如果不是，则终止循环。对于每一个左端点和对应的右端点范围，计算可以形成的移除递增子数组数量，并累加到总数中。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
算法中提到'计算初始的可移除递增子数组个数'时，为什么使用`n - r + (1 if r > 0 else 0)`这种计算方式？
▷🦆
如果数组中所有元素都是递增的，`r`的初始值设定会不会影响算法的执行或结果？
▷🦆
在计算对应子数组个数时，为什么使用`n - r + (0 if r == l + 1 else 1)`来计算？这里的条件`(0 if r == l + 1 else 1)`具体是基于什么考虑？
▷