- 博客主页:音符犹如代码
- 系列专栏:算法练习
- 关注博主,后期持续更新系列文章
- 如果有错误感谢请大家批评指出,及时修改
- 感谢大家点赞👍收藏⭐评论✍
目录
解题思路
解题方法
时间复杂度
空间复杂度
Code
解题思路
incremovableSubarrayCount 方法通过两层循环遍历数组 nums 的所有可能子数组。对于每个子数组,调用 isRemovableIncreasing 方法来判断移除该子数组后剩余元素是否严格递增。
isRemovableIncreasing 方法创建一个新的数组来存储移除指定子数组后的元素,然后通过遍历这个新数组来检查其是否严格递增
解题方法
采用暴力枚举的方式,遍历所有可能的子数组,并通过创建新数组和逐个比较元素的方式来判断剩余元素的递增性。
时间复杂度
O(n*3)
空间复杂度
O(n)
Code
class Solution {
public int incremovableSubarrayCount(int[] nums) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
if (isRemovableIncreasing(nums, i, j)) {
count++;
}
}
}
return count;
}
public boolean isRemovableIncreasing(int[] nums, int start, int end) {
int[] newNums = new int[nums.length - (end - start + 1)];
int newIndex = 0;
for (int i = 0; i < nums.length; i++) {
if (i < start || i > end) {
newNums[newIndex++] = nums[i];
}
}
for (int i = 1; i < newNums.length; i++) {
if (newNums[i] <= newNums[i - 1]) {
return false;
}
}
return true;
}
}