笔记仓库

正常人的正常笔记集

LC891的变体:求所有连续子集的极差之和

在上周日的Weekly Contest 98 中的压轴题Sum of Subsequence Widths(以下简称母题)题解中我特意强调了这里的subsequence只是子集,并不要求所有元素之间的连续,所以做起来会更容易。今天志成 @_FollowYourHeart_问了个很好的问题:如果题目改成连续子集应该怎么做比较好?

问题背景

有一个整数数组A,其中的元素不保证不相同。对一个非空数组来说,宽度定义为该集合的最大值减去最小值的结果,求A的所有连续子数组的宽度之和。

这里的连续子数组指对于任意$1 \le i \le j \le n$,从A取下标从$i$到$j$的任意子数组,这里标记为$A[i:j]$(注意这个符号区别于部分编程语言的从0开始计数索引以及不包含上界的切片标记A[i:j]

母题中给的Example 1输入[2,1,3]包含的连续子数组只有[2],[1],[3],[2,1],[1,3],[2,1,3]而没有原来的[2,3]

整个问题要求的就是$$\sum\limits_{i = 1}^n {\sum\limits_{j = i}^n {\max (A[i:j]) - \min (A[i:j])} }$$众所周知,当$i=j$即子数组长度为1时,宽度(极差)为0,所以可以只考虑$i<j$的情况,把上式进一步改写为$$\sum\limits_{i = 1}^{n-1} {\sum\limits_{j = i+1}^n {\max (A[i:j]) - \min (A[i:j])} }$$对于Example 1来说只需要考虑子数组[2,1],[1,3],[2,1,3]宽度,分别为1,2,2,最终结果为5

暴力搜索

最直接的方法,根据上式的两个求和标记直接写一个二层循环进行求和:

1
2
3
4
5
6
7
def sum_of_widths_naive(A):
n = len(A)
res = 0
for i in range(n):
for j in range(i + 1, n):
res += max(A[i:j + 1]) - min(A[i:j + 1])
return res

内层循环也分别求两次最值,所以时间复杂度很显然是$o(n^3)$

直觉的改进

因为内层循环的存在,子数组都是逐个扩大的,所以利用minmax函数对子数组进行求最值的操作是多余的,完全可以维护两个临时变量作为当前的最大值和最小值。

1
2
3
4
5
6
7
8
9
def sum_of_widths_improved(A):
n=len(A)
res=0
for i in range(n-1):
min_num,max_num=A[i],A[i]
for j in range(i,n):
min_num,max_num=min(min_num,A[j]),max(max_num,A[j])
res+=max_num-min_num
return res

这样就可以把时间复杂度降低到$o(n^2)$了

排序+缩小搜索范围

和母题一样,接下来可以试着考虑一下每一对$A[i],A[j]$作为最小值和最大值的子数组有多少个,即$A[j]-A[i]$被加了多少次,正如我在母题的题解里面所说的它们扮演了什么角色?

首先我们来看整个A数组的最大值和最小值,记它们的下标分别为$x$和$y$,它们规定了多少个连续子数组的极差呢?为了方便讨论,我们假设$x<y$,即同时包含这两个数的最小子数组为$A[x:y]$,而$A[y]-A[x]$已经是A的最大宽度了,所有包含$A[x:y]$的子数组的宽度也都是$A[y]-A[x]$,这些数组的起点最小为1最大为$x$,终点最小为$y$最大为$n$

绿色部分为上面提到的最小子数组,宽度为A[y]-A[x]的所有子数组必须包含全部的绿色部分,除此之外可以包含从x开始向左任意长度的灰色部分,也可以同时包含y开始向右任意长度的灰色部分

那么一共有$x(n-y+1)$个连续子数组的宽度为$A[y]-A[x]$,接下来我们可以试着逐渐缩小目标宽度,不妨从减小最大值开始入手:

假设$A[y’]$是A的第二大值,仅次于$A[y]$,有多少子数组是以$A[y]-A[x]$作为宽度的?

Case 1

首先考虑一种比较简单的情况,$y’>y$

这时所有同时包含$A[x]$和$A[y’]$的连续子数组(即使是最小的$A[x:y’]$)必然包括$A[y]$,那么这些数组的宽度则以$A[y]-A[x]$进行计算,所以宽度为$A[y’]-A[x]$的连续子数组不存在。

Case 2

当$y’<y$时,我们继续沿用上面为了方便讨论的规定最大值的坐标大于最小值的坐标,即$y’>x$

我们知道以二者的差为宽度的子数组一定同时包含这两个元素,但同时多了一个限制:数组的最大值不能超过$A[y’]$,即数组的重点下标必须小于$y$,结合前文整理一下,这些数组的起点最小为1最大为$x$,重点最小为$y$最大为$y’-1$

子数组必须包含绿色部分的全部,从绿色部分开始延伸的任意长度的灰色部分,但不能延伸到任何红色的部分

共有$x(y-y’)$个连续子数组。

当$x$不变时,随着连续取更小的$A[y’]$,为了保证$A[y’]$是子数组中的最大值,子数组不能“横跨”的坐标值也越来越多。即使去掉$y_i>x$的假设,也可以理解这个缩小范围的原理,无论是上界也好,下界也好,每次落到这个区间内的$y$都会带来一次边界的更新,使得下一个需要用来计算宽度的$y$所能落到的下标区间越来越狭窄。

不妨跳出上面的全局最值的局限,考虑对于任意满足$A[x]<A[y]$的$x$和$y$,如何找出所有以$A[y]-A[x]$为宽度的连续子数组?那么上文对于全局最值的讨论其实也解决了这个问题的一部分,即当我们知道以$A[x]$为最小值,$A[y]$为最大值的最大长度连续数组时我们就可以用上面的方法计算了。假设这个最大数组的起点为$s+1$,终点为$e-1$($s$和$e$分别在代码中变量名为startend),也就是$A[s]$和$A[e]$一定是小于$A[x]$或大于$A[y]$的值,而$A[s+1:e-1]$一定落在$A[x]$与$A[y]$之间。那么以$A[y]-A[x]$为宽度的子数组下标的起点为$[s+1,x]$,终点为$[y,e-1]$

左右都不可以延伸到红色部分

固定$x$不变时,根据上文的讨论,可以按照$A[y]$的降序取$y$,落在区间$[s+1,e-1]$时完成计算后,如果$y < x$则更新$s$的值为$y$,如果$y>x$则更新$e$的值为$y$。


对每轮$x$取值开始之前,需要先找准边界保证$A[x]$就是这个最大长度区间的最小值,那么可以先按照$A[x]$升序排序,在之前取过的$x’$中小于当前$x$的最大$x’$即为$s$,大于当前$x$的最小$y’$即为$e$,直观上来说这是两个距离$x$ 最近 的且满足$A[x’]<A[x]$的下标。

当然,$s$和$e$需要分别被初始化为比第一个下标更小1的值,以及比最后一个下标更大1的值,这样可以保证在还没有更新边界时,所有元素都被包含在了需要搜索的范围内。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def sum_of_widths(A):
n = len(A)
pos = sorted(range(n), key=lambda i: A[i])
res = 0
for i in range(n - 1):
x = pos[i]
start = max([p for p in pos[:i] if p < x] + [-1])
end = min([p for p in pos[:i] if p > x] + [n])
for j in range(n - 1, i, -1):
y = pos[j]
if y > end or y < start:
continue
if x < y:
res += (end - y) * (x - start) * (A[y] - A[x])
end = y
else:
res += (end - x) * (y - start) * (A[y] - A[x])
start = y
if end - start == 2:
break
return res

时间复杂度为$o(n^2)$,空间复杂度为$o(n)$

伪单遍遍历*

8/22更新内容

本小节为8/22看到志成回复给我他的想法:找到每个元素在哪些区间内是最大值/最小值,方法是对每个A[i]维护两个个单调栈,分别向左和向右找到第一个大于/小于A[i]的坐标se,那么A[i]就只在(i-s)*(e-i)个区间作为最大值/最小值。

其实这个找A[i]被加多少次和被减多少次的思路是最接近母题最终解法(sort + one pass)的,那就索性不用单调栈了,其实是我实在太懒了不想费脑子写,直接按照母题写单次遍历了。

在上文我们提到每轮外层循环开始对每个$x$更新$s$和$e$的规则,这是为了保证$x$在内层循环开始前是$[s+1,e-1]$内所有包含$x$的区间的最小值。其实这里如果要保证某个$x$是某个范围内所有包含$x$的子集的最大值也是同理,按$A[i]$照降序排序,对每个$A[i]$找到在$i$左边的小于$i$的最大值作为$s$,当然这里是为了保证$A[i]$为最大值$A[y]$所以为了区分前文把这个$s$记作$s_y$,前文的那个使得$A[i]$最小的$s$记作$s_x$;同理找到在$i$左边且大于$i$的最小值作为$e_y$,那么就容易计算$A[i]$一共被加了多少次和减了多少次。

1
2
3
4
5
6
7
8
9
10
11
def sum_of_widths_one_pass(A):
n = len(A)
pos = sorted(range(n), key=lambda i: A[i])
res = 0
for i, v in enumerate(pos):
s_x = max([p for p in pos[:i] if p < v] + [-1])
e_x = min([p for p in pos[:i] if p > v] + [n])
s_y = max([p for p in pos[i:] if p < v] + [-1])
e_y = min([p for p in pos[i:] if p > v] + [n])
res += ((e_y - v) * (v - s_y) - (e_x - v) * (v - s_x)) * A[v]
return res

虽然看上去有点像母题优雅的one pass,但实际上循环体里面的求最值依然$o(n)$遍历不可避,所以最终还是$o(n^2)$的时间复杂度和$o(n)$的空间复杂度。

单调栈

8/24 重要更新

志成已经在评论区给出了详细的解释和实现,蠢萌,不 蠢而不萌的废物本人我艰难地看完,后知后觉的感叹这确实是一个巧妙的$o(n)$方法。详细讨论见评论区,再次感谢志成大佬~

还是我们之前所说找A[i]在多大范围内是最小值。先看一侧,也就是在A[i]右边大于A[i]值的最小坐标。

单调栈是一个保证自顶而下单调递增或者递减的栈,维护这个栈只需要(假设自顶而下递减,即栈顶为最大元素):

  1. 如果当前元素小于栈顶,则弹出元素直至当前元素大于栈顶并进入2
  2. 如果当前元素大于栈顶,则直接压入栈内

当我们进行一次对A的正序遍历,对每个元素A[i]来说,弹栈至满足要求2的时候,当前栈顶的元素也是左边最近的大于A[i]的值,即前文使用的s_x,这个思路是志成的实现中所使用的,我在实现的写法上与他略有不同:对于所有这些被弹出的元素A[j],令它们被弹出的A[i]是右边距离它们最近的比它们大的值,所以在弹栈操作时每弹出一个就可以更新j下标的e_xi。当然不要忘记最后还没有被弹出的元素,他们右边最近的更小值不存在,可以统一更新为n。如此一来,每个元素至多被压入或者弹出一次,即每次遍历中维护整个mono_stack的总开销为$o(n)$。

通过遍历顺序和单调栈单调性的改变,四次$o(n)$的线性扫描就可以得到每个下标的s_x,e_x,s_ye_y了。最后的再来第五次遍历,根据上文的公式计算每个A[i]在结果中被加减过了多少次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def sum_of_widths_mono_stack(A):
n = len(A)
res = 0
s_x, s_y, e_x, e_y = [-1] * n, [-1] * n, [n] * n, [n] * n
mono_stack = []

for i in range(n):
while mono_stack and A[mono_stack[-1]] >= A[i]:
e_x[mono_stack.pop()] = i
mono_stack.append(i)

mono_stack = []

for i in range(n - 1, -1, -1):
while mono_stack and A[mono_stack[-1]] > A[i]:
s_x[mono_stack.pop()] = i
mono_stack.append(i)

mono_stack = []

for i in range(n):
while mono_stack and A[mono_stack[-1]] <= A[i]:
e_y[mono_stack.pop()] = i
mono_stack.append(i)

mono_stack = []

for i in range(n - 1, -1, -1):
while mono_stack and A[mono_stack[-1]] < A[i]:
s_y[mono_stack.pop()] = i
mono_stack.append(i)

for (i, v) in enumerate(A):
res += ((e_y[i] - i) * (i - s_y[i]) - (e_x[i] - i) * (i - s_x[i])) * v

return res

除此以外,我在评论区的讨论也提到过,比较麻烦的一点就是不保证A内所有元素不重复,所以在单调栈弹栈时的比较运算是否该取等号这个问题上需要格外谨慎。在正序和逆序遍历中同时取等号或者同时不取会导致被重复计算或忽略,所以需要在同一个方向上保留等号,而在另一个方向上不保留,也就是说上面对于操纵mono_stack的四个for循环中while语句的符号只能是>=,>,<=,<>,>=,<,<=

总结

三种方法都可以保证输出正确的结果,比如使用随机测试用例1

1
test = [868, 1380, 63, 948, 1065, 796, 1130, 895, 1371, 1170]

可以看到三个函数的输出结果都为37672,虽然花费了巨大的笔墨讲解第三种方法,但实际上从复杂度来看相较前两者似乎没有什么优势。不过这样的解法看上去比较舒服的地方,至少相对前两种方法里线性等宽的遍历,它可以仅在几次循环中就大幅度缩小下一轮需要遍历的范围,直觉上让人感觉轻松的多(有吗?笑)

相比被更改前的母题,这个问题的处理其实麻烦的多,我试着和其他人讨论,搜索现有资料,都没有找到特别巧妙的方法,也很可能是我的能力太有限,总之有任何可能的想法欢迎在评论或者邮件提出。母题没有连续的限定,同样使用暴力搜索时需要的开销为$o(2^n)$看上去更复杂,但实际在没有连续这个限制时,数组元素之间的顺序是没有意义的,所以母题可以在排序后只考虑每个元素和哪些元素的组合是被加,哪些是被减,但在这里却必须考虑每个元素在原数组中的位置,它与任何一个元素的组合里面能不能含有其他元素,所以无法放开手脚去做,我只能这么畏畏缩缩地用了这样一个既不效率又不优雅的算法。

总之,谢谢志成提出的好问题。也希望这篇文章能够抛砖引玉,读者能提供出更漂亮的方法2