我試圖在分治演算法方面做得更好，并以下面的這個演算法為例。給定一個陣列_in和某個長度，l它會找到一個子陣列的起點，使得該子陣列_in[_min_start,_min_start l]中的最低值可能是最高的。我提出了一個無分而治之的解決方案，我想知道如何將其轉換成一個將陣列分成更小的部分（分而治之）的解決方案。
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它將回傳起始位置 6（導致陣列[3,9,8]）。
uj5u.com熱心網友回復：
我將 _in 和 l 重命名為更清晰的名稱 A 和 k。
分而治之
將陣列分成兩半。遞回求解左半部和右半部。尚未考慮的子陣列跨越中間，即它們是左側部分的后綴加上右側部分的前綴。計算左半部分的 k-1 后綴最小值和右半部分的 k-1 前綴最小值。這允許您以 O(1) 時間計算每個長度為 k 的中間交叉子陣列的最小值。整個陣列的最佳子陣列是左最佳、右最佳和交叉最佳中的最佳子陣列。
我相信運行時間是 O(n)。正如 Ellis 所指出的，在遞回中，子陣列可以變得小于 k。這種情況需要 O(1) 時間來回傳“這里沒有任何 k 長度的子陣列”的等價物。所以時間是：
T(n) = { 2 * T(n/2) O(k) if n >= k
{ O(1) otherwise
對于任何 0 <= k <= n 我們有 k=n c且 0 <= c <= 1。那么呼叫次數是 Θ(n 1-c ) 并且每個呼叫自己的作業需要 Θ(n c ) 時間，總共 Θ(n) 時間。
獨角獸
不是分而治之，而是 O(n)。
滑動視窗，表示視窗中具有嚴格遞增陣列值的（已排序）索引的雙端佇列。滑動視窗以包含新值時A[i]：
- 如果滑動使它掉出視窗，則從雙端佇列中洗掉第一個索引。
- 洗掉陣列值大于 的索引
A[i]。（它們再也不能成為視窗的最小值了。） - 包括新索引
i。 - 仍在雙端佇列中的第一個索引是當前視窗最小值的索引。使用它來更新整體結果。
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)
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313538.html