统计定界子数组的数目

记住「bad 截左界、lastMin/lastMax 给右界;每步加 max(0, min(lm,lx) − bad)」,下面每一格都在套它。

这一行是数组。bad、lastMin、lastMax 一开始都是 −1(还没遇到)。右指针从左往右一格格扫,我们盯着这三个位置和 ans 怎么变。

右指针到第 0 位,值 1,它正好是 minK。它能当 minK,把对应的最近位置更新到 0(绿色)。

以第 0 位为右端时,minK 或 maxK 还没同时出现,凑不出合法左端,这一步贡献 0,ans 不变,仍是 0。

右指针到第 1 位,值 3,它普通(在界内)。它在界内、但既不是 minK 也不是 maxK,三个位置都不变。

以第 1 位为右端时,minK 或 maxK 还没同时出现,凑不出合法左端,这一步贡献 0,ans 不变,仍是 0。

右指针到第 2 位,值 5,它正好是 maxK。它能当 maxK,把对应的最近位置更新到 2(绿色)。

以第 2 位为右端,合法左端要在 bad=-1 右边、又不能晚于 min(lastMin,lastMax)=0,也就是下标 0 到 0 这 1 个起点,每个都框出一个合法子数组。答案加 1,累计 1。

右指针到第 3 位,值 2,它普通(在界内)。它在界内、但既不是 minK 也不是 maxK,三个位置都不变。

以第 3 位为右端,合法左端要在 bad=-1 右边、又不能晚于 min(lastMin,lastMax)=0,也就是下标 0 到 0 这 1 个起点,每个都框出一个合法子数组。答案加 1,累计 2。

右指针到第 4 位,值 7,它越界。这是个越界数,合法子数组绝不能跨过它,把 bad 推到 4(红色)。

以第 4 位为右端时,min(lastMin,lastMax)=0 没越过 bad=4,凑不出合法左端,这一步贡献 0,ans 不变,仍是 2。

右指针到第 5 位,值 5,它正好是 maxK。它能当 maxK,把对应的最近位置更新到 5(绿色)。

以第 5 位为右端时,min(lastMin,lastMax)=0 没越过 bad=4,凑不出合法左端,这一步贡献 0,ans 不变,仍是 2。

右指针到第 6 位,值 1,它正好是 minK。它能当 minK,把对应的最近位置更新到 6(绿色)。

以第 6 位为右端,合法左端要在 bad=4 右边、又不能晚于 min(lastMin,lastMax)=5,也就是下标 5 到 5 这 1 个起点,每个都框出一个合法子数组。答案加 1,累计 3。

右指针到第 7 位,值 4,它普通(在界内)。它在界内、但既不是 minK 也不是 maxK,三个位置都不变。

以第 7 位为右端,合法左端要在 bad=4 右边、又不能晚于 min(lastMin,lastMax)=5,也就是下标 5 到 5 这 1 个起点,每个都框出一个合法子数组。答案加 1,累计 4。

右指针到第 8 位,值 5,它正好是 maxK。它能当 maxK,把对应的最近位置更新到 8(绿色)。

以第 8 位为右端,合法左端要在 bad=4 右边、又不能晚于 min(lastMin,lastMax)=6,也就是下标 5 到 6 这 2 个起点,每个都框出一个合法子数组。答案加 2,累计 6。

扫完全程,把每个右端点贡献的「max(0, min(lastMin,lastMax) − bad)」加起来,一共 6 个子数组的最小值正好是 1、最大值正好是 5。只用三个位置变量、一遍扫完,O(n)。

边界:minK=maxK 时退化成「无越界即可」;缺 minK 或 maxK、或全越界都返回 0。

面试常考:用「以 i 结尾」论证不重不漏,以及为何只需记最近位置。