统计移除递增子数组的数目 I
难度:
标签:
题目描述
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 <= 501 <= nums[i] <= 50
代码结果
运行时间: 30 ms, 内存: 15.9 MB
/*
* 思路：
* 1. 使用Java Stream API来生成所有可能的子数组。
* 2. 对每一个子数组，移除后检查剩余数组是否严格递增。
* 3. 统计满足条件的子数组数量。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class SolutionStream {
public long countIncreasingSubarrays(int[] nums) {
int n = nums.length;
return IntStream.range(0, n)
.boxed()
.flatMap(i -> IntStream.range(i, n)
.mapToObj(j -> removeSubarray(nums, i, j)))
.filter(this::isStrictlyIncreasing)
.count();
}
private int[] removeSubarray(int[] nums, int start, int end) {
return IntStream.range(0, nums.length)
.filter(i -> i < start || i > end)
.map(i -> nums[i])
.toArray();
}
private boolean isStrictlyIncreasing(int[] nums) {
return IntStream.range(1, nums.length)
.allMatch(i -> nums[i] > nums[i - 1]);
}
}
解释
方法:
该题解采用滑动窗口的方法来寻找所有可能的子数组，并检查每个子数组是否为移除递增子数组。具体做法是使用双指针技术，其中外层循环的指针left代表子数组的起始位置，内层循环的指针right代表子数组的结束位置。对于每一个由left和right定义的子数组，调用getAscFlag函数来检查除去这个子数组外，剩余的数组部分是否严格递增。如果是，则计数器ans增加1。最终，返回ans，即所有满足条件的子数组数量。
时间复杂度:
O(n^3)
空间复杂度:
O(1)
代码细节讲解
🦆
在函数`getAscFlag`中使用`float('-inf')`初始化变量`l`的原因是什么？
▷🦆
为什么整个算法选择使用双层循环遍历所有可能的子数组？这种方法在最坏情况下的时间复杂度是多少？
▷🦆
在检查剩余数组是否严格递增时，`getAscFlag`函数是否考虑了数组的边界情况，如子数组在数组的开始或结束位置？
▷