• 博客主頁：音符猶如代碼
• 系列專欄：算法練習
• 關注博主，后期持續更新系列文章
• 如果有錯誤感謝請大家批評指出，及時修改
• 感謝大家點贊👍收藏?評論?

?

?

目錄

解題思路

解題方法

時間復雜度

空間復雜度

Code?

---

解題思路

該問題的目標是計算給定數組中，可以移除的遞增子數組的數量。一個子數組如果可以移除，意味著它在原數組中是遞增的。為了解決這個問題，我采用了以下策略：

1. 尋找最長遞增前綴：首先，我尋找數組中從第一個元素開始的最長遞增子序列（前綴）。這是因為任何包含這個前綴的子數組都是遞增的，因此可以移除。

2. 處理特殊情況：如果整個數組（除了最后一個元素外）都是遞增的，那么任何非空子數組都可以移除。在這種情況下，直接返回所有可能的子數組數量，即?n*(n+1)/2。

3. 枚舉遞增后綴：如果數組不是整體遞增的，那么我從數組的末尾開始，嘗試找到可以與前面找到的最長遞增前綴相結合的遞增后綴。對于每個這樣的后綴，我計算可以與它結合的最長遞增前綴的長度。

4. 累加可移除子數組數量：對于每個找到的遞增后綴，我將其與兼容的前綴組合，形成可以移除的遞增子數組，并累加這些組合的數量。

解題方法

1. 使用findLongestIncreasingPrefix方法找到最長遞增前綴

2. 檢查是否整個數組（除最后一個元素外）都是遞增的。如果是，直接返回所有可能的子數組數量

3. 如果不是整體遞增，使用循環從數組末尾開始查找遞增后綴

4. 對于每個遞增后綴，使用findCompatiblePrefixLength方法找到可以與它結合的最長遞增前綴

5. 累加可以與當前后綴組成遞增子數組的前綴數量

6. 返回累加的數量作為結果

時間復雜度

• 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指向的元素）  }  
}

?

??A miss is as good as a mile