Back to Leetcode

Readme

Binary_Search/2972.Count-the-Number-of-Incremovable-Subarrays-II/Readme.md

latest1.4 KB
Original Source

2972.Count-the-Number-of-Incremovable-Subarrays-II

本题最直观的考虑,就是将数组分成三段(考虑1-index):前段[1:i],中段[i+1:j-1],以及后段[j:n]。其中要移走中段,而前段和后段必须各自都是严格递增的。于是我们可以找到i的最大位置记做L,以及j的最小位置记做R。

cpp
  int l = 1;
  while (l<=n)
  {
      if (nums[l]<nums[l+1]) l++;
      else break;
  }
  int r = n;
  while (r>0)
  {
      if (nums[r]>nums[r-1]) r--;
      else break;
  }

对于[1:L]里的每一个位置i,我们可以在[R,n]用二分找到恰好大于nums[i]的位置j。那么符合条件的后段的左边界可以是j,j+1,...,n,总共有n+1-j个。

但是以上的思考意识强制要求前段、中段、后段都不能为空,而忽略了对应的三种情况:前段为空,中段为空、或者后段为空。需要额外考虑。

  1. 如果中段为空,那么说明nums整体都是递增的,直接返回nums里的子区间的数目:n(n-1)/2+n.
  2. 如果前端为空,或者后端为空,我们可以有一个巧妙的处理,使得之前的逻辑依然适用。在nums前添加一个无穷小(index是0),后面添加一个无穷大(index是n+1)。这样,i的遍历可以从0开始(意味着其实左段为空);而在[R:n+1]区间里进行二分的过程中可能会找到n+1这个位置(即认为后段的左边界是n+1),这其实就意味着允许了后段为空。