Leetcode 第 120 场双周赛 Problem C 统计移除递增子数组的数目 II(Java + 双指针 + 前缀和)
2023-12-24 06:03:01
题目
- 统计移除递增子数组的数目 II
- 给你一个下标从 0 开始的 正 整数数组 nums 。
- 如果 nums 的一个子数组满足:移除这个子数组后剩余元素 严格递增 ,那么我们称这个子数组为 移除递增 子数组。比方说,[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组,因为移除该子数组后,[5, 3, 4, 6, 7] 变为 [5, 6, 7] ,是严格递增的。
- 请你返回 nums 中 移除递增 子数组的总数目。
- 注意 ,剩余元素为空的数组也视为是递增的。
- 子数组 指的是一个数组中一段连续的元素序列。
- 1 <= nums.length <= 10 ^ 5
- 1 <= nums[i] <= 10 ^ 9
解法
Java + 双指针 + 前缀和:
第 1 步:
- 分析题意可得,如果移除区间 [x,y] 后剩下为递增数组,那么移除 [x-1,y]、[x-2,y]… 后也剩下递增数组,
- 因此我们想到枚举每个 y,找到最大的 x,然后 [0,x] 均可作为移除的左区间
第 2 步:
- 从左往右枚举 y 时,x 满足条件需要
- [y+1, n-1] 为递增数组
- [0,x-1] 也为自增数组
- nums[x-1] < nums[y+1]
- 根据上述可以发现 y 增大时,最大的 x 要么不变、要么增加,使用双指针的方式求解
第 3 步:
- 具体做法:
- 预处理前缀与后缀是否满足严格递增,
- 枚举 y 时,如果前缀与后缀均递增,找到最大的 x,
- 可以删除 [0,y] … [x,y],因此答案加上 x+1
- 时间复杂度:O(n),空间复杂度:O(n)
代码
/**
* Java + 双指针 + 前缀和:
*
* 第 1 步:
* 分析题意可得,如果移除区间 [x,y] 后剩下为递增数组,那么移除 [x-1,y]、[x-2,y]... 后也剩下递增数组,
* 因此我们想到枚举每个 y,找到最大的 x,然后 [0,x] 均可作为移除的左区间
*
* 第 2 步:
* 从左往右枚举 y 时,x 满足条件需要
* 1. [y+1, n-1] 为递增数组
* 2. [0,x-1] 也为自增数组
* 3. nums[x-1] < nums[y+1]
* 根据上述可以发现 y 增大时,最大的 x 要么不变、要么增加,使用双指针的方式求解
*
* 第 3 步:
* 具体做法:
* 预处理前缀与后缀是否满足严格递增,
* 枚举 y 时,如果前缀与后缀均递增,找到最大的 x,
* 可以删除 [0,y] ... [x,y],因此答案加上 x+1
*
* 时间复杂度:O(n),空间复杂度:O(n)
*
*/
public long incremovableSubarrayCount(int[] nums) {
int n = nums.length;
// 前缀 [0,i] 是否为递增数组
boolean[] prefix = new boolean[n];
prefix[0] = true;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
prefix[i] = true;
} else {
break;
}
}
// 后缀 [i,n-1] 是否为递增数组,为方便处理多加一个 n
boolean[] suffix = new boolean[n + 1];
suffix[n] = true;
suffix[n - 1] = true;
for (int i = n - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
suffix[i] = true;
} else {
break;
}
}
long res = 0L;
// 枚举移除的右端点时,最大的左端点值
int maxLeft = 0;
for (int right = 0; right < n; right++) {
// 左端点小于右端点,左端点递增,右端点后面递增,右端点后面均大于左端点
while (right > maxLeft && prefix[maxLeft] && suffix[right + 1]
&& (right == n - 1 || nums[right + 1] > nums[maxLeft])) {
maxLeft++;
}
// maxLeft++ 时已经保证了左端点递增,因此只需要看右端点后面递增即可
if (suffix[right + 1]) {
res += maxLeft + 1;
}
}
return res;
}
文章来源:https://blog.csdn.net/qq_33530115/article/details/135177271
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!