第 120 场力扣夜喵双周赛

统计移除递增子数组的数目 II

题目

输入长度为 \(n\) 的数组 \(a\)，输出子数组的数目，使得移除该子数组之后剩余的数是严格递增的，空数组也被认为是递增的。

数据范围：\(1\leq n\leq 10^{5}\)，\(1\leq a_{i}\leq 10^{9}\)。

思路

首先找到第一个满足 \(a_{i}>=a_{i+1}\) 的下标 \(i\)。如果 \(i=n-1\)，则表示可以移除任意子数组，直接返回 \(\frac{n(n-1)}{2}\)。否则，我们需要移除一个子数组使得剩余前缀和后缀分别递增，并且前缀的右端点小于后缀的左端点。可以使用双指针，一个指针枚举后缀的左端点 \(j\)，另一个指针从 \(i\) 开始左移，寻找满足条件的前缀的右端点 \(i\)，然后将 \(i+2\) 添加到答案中，重复此过程直到 \(a_{j}>=a_{j+1}\)。