如何将解决方案转化为分而治之（找到具有最大、最小值的子数组）
How to translate a solution into divide-and-conquer (finding a sub array with the largest, smallest value)
我正在努力提高分而治之的算法，并以下面的算法为例。给定一个数组 _in 和一些长度 l 它找到子数组 _in[_min_start,_min_start+l] 的起点，使得该子数组中的最低值是可能的最高值。我想出了一个 none 分而治之的解决方案，我想知道如何将其转化为将数组分成更小的部分（分而治之）的解决方案。
def main(_in, l):
_min_start = 0
min_trough = None
for i in range(len(_in)+1-l):
if min_trough is None:
min_trough = min(_in[i:i+l])
if min(_in[i:i+l]) > min_trough:
_min_start = i
min_trough = min(_in[i:i+l])
return _min_start, _in[_min_start:_min_start+l]
例如对于数组 [5, 1, -1, 2, 5, -4, 3, 9, 8, -2, 0, 6] 和长度为 3 的子数组，它将 return 从位置 6 开始（导致数组 [3,9,8]）。
三个 O(n) 解决方案和一个基准
请注意，我将 _in 和 l 重命名为更清晰的名称 A 和 k。
解决方案 1：分而治之
将数组分成两半。递归求解左半边和右半边。尚未考虑的子数组穿过中间，即它们是左侧部分的后缀加上右侧部分的前缀。计算左半部分的 k-1 后缀最小值和右半部分的 k-1 前缀最小值。这允许您在 O(1) 时间内计算每个长度为 k 的中间交叉子数组的最小值。整个数组的最佳子数组是左最佳、右最佳和交叉最佳中的最佳。
我相信运行时间是 O(n)。正如埃利斯指出的那样，在递归中，子数组可以变得小于 k。这种情况需要 O(1) 时间 return 相当于 “这里没有任何 k 长度的子数组”。所以时间是：
T(n) = { 2 * T(n/2) + O(k) if n >= k
{ O(1) otherwise
对于任何 0 <= k <= n 我们有 k=nc 其中 0 <= c <= 1。那么调用次数是 Θ(n1-c) 并且每个调用自己的工作需要 Θ(nc) 时间，总共 Θ(n) 时间。
发布了一个question关于复杂性的信息。
Python 实施：
def solve_divide_and_conquer(A, k):
def solve(start, stop):
if stop - start < k:
return -inf,
mid = (start + stop) // 2
left = solve(start, mid)
right = solve(mid, stop)
i0 = mid - k + 1
prefixes = accumulate(A[mid:mid+k-1], min)
if i0 < 0:
prefixes = [*prefixes][-i0:]
i0 = 0
suffixes = list(accumulate(A[i0:mid][::-1], min))[::-1]
crossing = max(zip(map(min, suffixes, prefixes), count(i0)))
return max(left, right, crossing)
return solve(0, len(A))[1]
解决方案 2：k 块
正如@benrg评论的那样，上面的分而治之是不必要的复杂。我们可以简单地处理长度为 k 的块。计算第一个块的后缀最小值和第二个块的前缀最小值。这允许在 O(1) 时间内找到这两个块中每个 k 长度子数组的最小值。对第二个和第三个块，第三个和第四个块等执行相同的操作。时间也是 O(n)。
Python 实施：
def solve_blocks(A, k):
return max(max(zip(map(min, prefixes, suffixes), count(mid-k)))
for mid in range(k, len(A)+1, k)
for prefixes in [accumulate(A[mid:mid+k], min, initial=inf)]
for suffixes in [list(accumulate(A[mid-k:mid][::-1], min, initial=inf))[::-1]]
)[1]
解决方案 3：Monoqueue
不是分而治之，而是我想出的第一个（并且知道是 O(n)）。
滑动 window，用 window 中严格递增数组值的双端队列（已排序）索引表示 window。滑动 window 以包含新值时 A[i]:
- 如果滑动使它脱离 window，则从双端队列中删除第一个索引。
- 删除数组值大于
A[i]的索引。 （它们再也不能是 window 中的最小值了。）
- 包括新索引
i。
- 仍在双端队列中的第一个索引是当前window的最小值的索引。用它来更新整体结果。
Python 实施：
from collections import deque
A = [5, 1, -1, 2, 5, -4, 3, 9, 8, -2, 0, 6]
k = 3
I = deque()
for i in range(len(A)):
if I and I[0] == i - k:
I.popleft()
while I and A[I[-1]] >= A[i]:
I.pop()
I.append(i)
curr_min = A[I[0]]
if i == k-1 or i > k-1 and curr_min > max_min:
result = i - k + 1
max_min = curr_min
print(result)
基准
从 0 到 9999 的 4000 个数字，k=2000：
80.4 ms 81.4 ms 81.8 ms solve_brute_force
80.2 ms 80.5 ms 80.7 ms solve_original
2.4 ms 2.4 ms 2.4 ms solve_monoqueue
2.4 ms 2.4 ms 2.4 ms solve_divide_and_conquer
1.3 ms 1.4 ms 1.4 ms solve_blocks
基准代码（Try it online!）：
from timeit import repeat
from random import choices
from itertools import accumulate
from math import inf
from itertools import count
from collections import deque
def solve_monoqueue(A, k):
I = deque()
for i in range(len(A)):
if I and I[0] == i - k:
I.popleft()
while I and A[I[-1]] >= A[i]:
I.pop()
I.append(i)
curr_min = A[I[0]]
if i == k-1 or i > k-1 and curr_min > max_min:
result = i - k + 1
max_min = curr_min
return result
def solve_divide_and_conquer(A, k):
def solve(start, stop):
if stop - start < k:
return -inf,
mid = (start + stop) // 2
left = solve(start, mid)
right = solve(mid, stop)
i0 = mid - k + 1
prefixes = accumulate(A[mid:mid+k-1], min)
if i0 < 0:
prefixes = [*prefixes][-i0:]
i0 = 0
suffixes = list(accumulate(A[i0:mid][::-1], min))[::-1]
crossing = max(zip(map(min, suffixes, prefixes), count(i0)))
return max(left, right, crossing)
return solve(0, len(A))[1]
def solve_blocks(A, k):
return max(max(zip(map(min, prefixes, suffixes), count(mid-k)))
for mid in range(k, len(A)+1, k)
for prefixes in [accumulate(A[mid:mid+k], min, initial=inf)]
for suffixes in [list(accumulate(A[mid-k:mid][::-1], min, initial=inf))[::-1]]
)[1]
def solve_brute_force(A, k):
return max(range(len(A)+1-k),
key=lambda start: min(A[start : start+k]))
def solve_original(_in, l):
_min_start = 0
min_trough = None
for i in range(len(_in)+1-l):
if min_trough is None:
min_trough = min(_in[i:i+l])
if min(_in[i:i+l]) > min_trough:
_min_start = i
min_trough = min(_in[i:i+l])
return _min_start # , _in[_min_start:_min_start+l]
solutions = [
solve_brute_force,
solve_original,
solve_monoqueue,
solve_divide_and_conquer,
solve_blocks,
]
for _ in range(3):
A = choices(range(10000), k=4000)
k = 2000
# Check correctness
expect = None
for solution in solutions:
index = solution(A.copy(), k)
assert 0 <= index and index + k-1 < len(A)
min_there = min(A[index : index+k])
if expect is None:
expect = min_there
print(expect)
else:
print(min_there == expect, solution.__name__)
print()
# Speed
for solution in solutions:
copy = A.copy()
ts = sorted(repeat(lambda: solution(copy, k), number=1))[:3]
print(*('%5.1f ms ' % (t * 1e3) for t in ts), solution.__name__)
print()
我正在努力提高分而治之的算法，并以下面的算法为例。给定一个数组 _in 和一些长度 l 它找到子数组 _in[_min_start,_min_start+l] 的起点，使得该子数组中的最低值是可能的最高值。我想出了一个 none 分而治之的解决方案，我想知道如何将其转化为将数组分成更小的部分（分而治之）的解决方案。
def main(_in, l):
_min_start = 0
min_trough = None
for i in range(len(_in)+1-l):
if min_trough is None:
min_trough = min(_in[i:i+l])
if min(_in[i:i+l]) > min_trough:
_min_start = i
min_trough = min(_in[i:i+l])
return _min_start, _in[_min_start:_min_start+l]
例如对于数组 [5, 1, -1, 2, 5, -4, 3, 9, 8, -2, 0, 6] 和长度为 3 的子数组，它将 return 从位置 6 开始（导致数组 [3,9,8]）。
三个 O(n) 解决方案和一个基准
请注意，我将 _in 和 l 重命名为更清晰的名称 A 和 k。
解决方案 1：分而治之
将数组分成两半。递归求解左半边和右半边。尚未考虑的子数组穿过中间，即它们是左侧部分的后缀加上右侧部分的前缀。计算左半部分的 k-1 后缀最小值和右半部分的 k-1 前缀最小值。这允许您在 O(1) 时间内计算每个长度为 k 的中间交叉子数组的最小值。整个数组的最佳子数组是左最佳、右最佳和交叉最佳中的最佳。
我相信运行时间是 O(n)。正如埃利斯指出的那样，在递归中，子数组可以变得小于 k。这种情况需要 O(1) 时间 return 相当于 “这里没有任何 k 长度的子数组”。所以时间是：
T(n) = { 2 * T(n/2) + O(k) if n >= k
{ O(1) otherwise
对于任何 0 <= k <= n 我们有 k=nc 其中 0 <= c <= 1。那么调用次数是 Θ(n1-c) 并且每个调用自己的工作需要 Θ(nc) 时间，总共 Θ(n) 时间。
发布了一个question关于复杂性的信息。
Python 实施：
def solve_divide_and_conquer(A, k):
def solve(start, stop):
if stop - start < k:
return -inf,
mid = (start + stop) // 2
left = solve(start, mid)
right = solve(mid, stop)
i0 = mid - k + 1
prefixes = accumulate(A[mid:mid+k-1], min)
if i0 < 0:
prefixes = [*prefixes][-i0:]
i0 = 0
suffixes = list(accumulate(A[i0:mid][::-1], min))[::-1]
crossing = max(zip(map(min, suffixes, prefixes), count(i0)))
return max(left, right, crossing)
return solve(0, len(A))[1]
解决方案 2：k 块
正如@benrg评论的那样，上面的分而治之是不必要的复杂。我们可以简单地处理长度为 k 的块。计算第一个块的后缀最小值和第二个块的前缀最小值。这允许在 O(1) 时间内找到这两个块中每个 k 长度子数组的最小值。对第二个和第三个块，第三个和第四个块等执行相同的操作。时间也是 O(n)。
Python 实施：
def solve_blocks(A, k):
return max(max(zip(map(min, prefixes, suffixes), count(mid-k)))
for mid in range(k, len(A)+1, k)
for prefixes in [accumulate(A[mid:mid+k], min, initial=inf)]
for suffixes in [list(accumulate(A[mid-k:mid][::-1], min, initial=inf))[::-1]]
)[1]
解决方案 3：Monoqueue
不是分而治之，而是我想出的第一个（并且知道是 O(n)）。
滑动 window，用 window 中严格递增数组值的双端队列（已排序）索引表示 window。滑动 window 以包含新值时 A[i]:
- 如果滑动使它脱离 window，则从双端队列中删除第一个索引。
- 删除数组值大于
A[i]的索引。 （它们再也不能是 window 中的最小值了。） - 包括新索引
i。 - 仍在双端队列中的第一个索引是当前window的最小值的索引。用它来更新整体结果。
Python 实施：
from collections import deque
A = [5, 1, -1, 2, 5, -4, 3, 9, 8, -2, 0, 6]
k = 3
I = deque()
for i in range(len(A)):
if I and I[0] == i - k:
I.popleft()
while I and A[I[-1]] >= A[i]:
I.pop()
I.append(i)
curr_min = A[I[0]]
if i == k-1 or i > k-1 and curr_min > max_min:
result = i - k + 1
max_min = curr_min
print(result)
基准
从 0 到 9999 的 4000 个数字，k=2000：
80.4 ms 81.4 ms 81.8 ms solve_brute_force
80.2 ms 80.5 ms 80.7 ms solve_original
2.4 ms 2.4 ms 2.4 ms solve_monoqueue
2.4 ms 2.4 ms 2.4 ms solve_divide_and_conquer
1.3 ms 1.4 ms 1.4 ms solve_blocks
基准代码（Try it online!）：
from timeit import repeat
from random import choices
from itertools import accumulate
from math import inf
from itertools import count
from collections import deque
def solve_monoqueue(A, k):
I = deque()
for i in range(len(A)):
if I and I[0] == i - k:
I.popleft()
while I and A[I[-1]] >= A[i]:
I.pop()
I.append(i)
curr_min = A[I[0]]
if i == k-1 or i > k-1 and curr_min > max_min:
result = i - k + 1
max_min = curr_min
return result
def solve_divide_and_conquer(A, k):
def solve(start, stop):
if stop - start < k:
return -inf,
mid = (start + stop) // 2
left = solve(start, mid)
right = solve(mid, stop)
i0 = mid - k + 1
prefixes = accumulate(A[mid:mid+k-1], min)
if i0 < 0:
prefixes = [*prefixes][-i0:]
i0 = 0
suffixes = list(accumulate(A[i0:mid][::-1], min))[::-1]
crossing = max(zip(map(min, suffixes, prefixes), count(i0)))
return max(left, right, crossing)
return solve(0, len(A))[1]
def solve_blocks(A, k):
return max(max(zip(map(min, prefixes, suffixes), count(mid-k)))
for mid in range(k, len(A)+1, k)
for prefixes in [accumulate(A[mid:mid+k], min, initial=inf)]
for suffixes in [list(accumulate(A[mid-k:mid][::-1], min, initial=inf))[::-1]]
)[1]
def solve_brute_force(A, k):
return max(range(len(A)+1-k),
key=lambda start: min(A[start : start+k]))
def solve_original(_in, l):
_min_start = 0
min_trough = None
for i in range(len(_in)+1-l):
if min_trough is None:
min_trough = min(_in[i:i+l])
if min(_in[i:i+l]) > min_trough:
_min_start = i
min_trough = min(_in[i:i+l])
return _min_start # , _in[_min_start:_min_start+l]
solutions = [
solve_brute_force,
solve_original,
solve_monoqueue,
solve_divide_and_conquer,
solve_blocks,
]
for _ in range(3):
A = choices(range(10000), k=4000)
k = 2000
# Check correctness
expect = None
for solution in solutions:
index = solution(A.copy(), k)
assert 0 <= index and index + k-1 < len(A)
min_there = min(A[index : index+k])
if expect is None:
expect = min_there
print(expect)
else:
print(min_there == expect, solution.__name__)
print()
# Speed
for solution in solutions:
copy = A.copy()
ts = sorted(repeat(lambda: solution(copy, k), number=1))[:3]
print(*('%5.1f ms ' % (t * 1e3) for t in ts), solution.__name__)
print()