- 博客主页：音符犹如代码
- 系列专栏：算法练习
- 关注博主，后期持续更新系列文章
- 如果有错误感谢请大家批评指出，及时修改
- 感谢大家点赞👍收藏⭐评论✍
目录
解题思路
解题方法
时间复杂度
空间复杂度
Code
解题思路
该问题的目标是计算给定数组中，可以移除的递增子数组的数量。一个子数组如果可以移除，意味着它在原数组中是递增的。为了解决这个问题，我采用了以下策略：
-
寻找最长递增前缀：首先，我寻找数组中从第一个元素开始的最长递增子序列（前缀）。这是因为任何包含这个前缀的子数组都是递增的，因此可以移除。
-
处理特殊情况：如果整个数组（除了最后一个元素外）都是递增的，那么任何非空子数组都可以移除。在这种情况下，直接返回所有可能的子数组数量，即
n*(n+1)/2。 -
枚举递增后缀：如果数组不是整体递增的，那么我从数组的末尾开始，尝试找到可以与前面找到的最长递增前缀相结合的递增后缀。对于每个这样的后缀，我计算可以与它结合的最长递增前缀的长度。
-
累加可移除子数组数量：对于每个找到的递增后缀，我将其与兼容的前缀组合，形成可以移除的递增子数组，并累加这些组合的数量。
解题方法
-
使用
findLongestIncreasingPrefix方法找到最长递增前缀 -
检查是否整个数组（除最后一个元素外）都是递增的。如果是，直接返回所有可能的子数组数量
-
如果不是整体递增，使用循环从数组末尾开始查找递增后缀
-
对于每个递增后缀，使用
findCompatiblePrefixLength方法找到可以与它结合的最长递增前缀 -
累加可以与当前后缀组成递增子数组的前缀数量
-
返回累加的数量作为结果
时间复杂度
findLongestIncreasingPrefix方法遍历数组一次，时间复杂度为O(n)- 主循环从数组末尾开始，最多遍历数组一次，对于每个位置，
findCompatiblePrefixLength可能再次遍历数组，因此总的时间复杂度为O(n^2)
空间复杂度
该算法只使用了几个变量来存储中间结果，没有使用额外的数据结构来存储大量数据，因此空间复杂度为O(1)
Code
class Solution { public long incremovableSubarrayCount(int[] a) { int n = a.length; // 找到最长递增前缀的长度 int prefixLength = findLongestIncreasingPrefix(a); // 如果整个数组都是递增的，则任何非空子数组都可以移除 if (prefixLength == n - 1) { // 返回所有可能的非空子数组的数量（使用等差数列求和公式） return (long)n * (n + 1) / 2; } long count = prefixLength + 2; // 初始化计数为整个前缀和整个数组本身 // 枚举所有可能的递增后缀 for (int suffixStart = n - 1; suffixStart >= 0 && a[suffixStart] < (suffixStart + 1 < n ? a[suffixStart + 1] : Integer.MAX_VALUE); suffixStart--) { // 找到能与当前后缀组成递增序列的最长前缀的长度 int compatiblePrefixLength = findCompatiblePrefixLength(a, prefixLength, suffixStart); count += compatiblePrefixLength + 1; // 累加可以组成的递增子数组数量 } return count; } // 辅助方法：找到最长递增前缀的长度 private int findLongestIncreasingPrefix(int[] a) { int n = a.length; int i = 0; while (i < n - 1 && a[i] < a[i + 1]) { i++; } return i; } // 辅助方法：找到与给定后缀兼容的最长前缀的长度 private int findCompatiblePrefixLength(int[] a, int initialPrefixLength, int suffixStart) { int prefixLength = initialPrefixLength; // 从之前找到的最长递增前缀开始向前查找，直到找到可以与后缀组成递增序列的前缀 while (prefixLength >= 0 && a[prefixLength] >= a[suffixStart]) { prefixLength--; } return prefixLength + 1; // 返回兼容前缀的长度（包括prefixLength指向的元素） }
} 