当题目要求移除一个subarray的时候,想象完整array变成了 pref + curr + surf,而问有多少个可以移除的时候也就是意味着,找有多少个curr. 我们可以想象不同的curr实际由一个curr的两端分别向外扩。但是这题因为有一个increasing的条件,无法确立一个specific的curr subarray, 但 可以确定的是只保留pref或surf时的curr的左右端点。
这里以pref为例,找到最长increasing的pref就可以确立curr的左端点, 让pref = [0, i], 那么curr = [i + 1,...], 这时候我们需要找右端点。
- 特殊情况如
i == n - 1时,我们则直接返回(n + 1) * n / 2。 右端点从最后往前枚举, 也就是j = n - 1,不难发现如果arr[j] < arr[i]的话就不构成increasing条件,所以与此同时我们需要同时迁移左端点使pref + surf构成increasing的条件。如果我们需要往前移动j则还需要满足arr[j] < arr[j + 1]. 所以这道题本质上是一道滑动窗口。