使用 Python 查找大小为 M 的最新组的程序
假设我们有一个数组arr，它保存了从1到n的数字排列。如果我们有一个大小为n的二进制字符串，并且最初它的所有位都设置为零。现在在从1到n的每一步i（二进制字符串和arr的索引都从1开始），位置arr[i]处的位被设置为1。我们还有另一个值m，我们需要找到最新的存在一组大小为m的步骤。这里的一组1表示一个连续的1子串，这样它就不能在任一方向上扩展。我们必须找到存在一组长度正好为m的组的最新一步。如果我们找不到任何这样的组，则返回-1。
因此，如果输入类似于arr=[3,5,1,2,4]m=3，则输出将为4，因为初始二进制字符串为“00000”，然后执行以下步骤-
“00100”，组：[“1”]
“00101”，组：[“1”，“1”]
“10101”，组：[“1”，“1”，“1”]
“11101”，组：[“111”，“1”]
“11111”，组：[“11111”]
这里存在一组大小为3的组的最新步骤是步骤4。
为了解决这个问题，我们将按照以下步骤操作-
n:=arr的大小
数量：=0
答案：=-1
l:=大小为n的数组，并用0填充
r:=大小为n的数组，并用0填充
对于0到n-1范围内的i，请执行
l[idx+r[idx]+1]:=当前
r[idx-l[idx]-1]:=cur
ans:=ans的最大值，i+1
数量:=数量-1
数量:=数量-1
当前：=1
idx:=arr[i]-1
如果r[idx]与m相同，则
如果l[idx]与m相同，则
cur:=cur+l[idx]+r[idx]
num:=num+cur与m相同
如果num>0，则
如果idx-l[idx]>0，则
如果idx+r[idx]
返回答案
让我们看看以下实现以获得更好的理解-
示例
def solve(arr, m):
n = len(arr)
num = 0
ans = -1
l = [0] * n
r = [0] * n
for i in range(n):
cur = 1
idx = arr[i] - 1
if r[idx] == m:
num -= 1
if l[idx] == m:
num -= 1
cur += l[idx] + r[idx]
num += cur == m
if num > 0:
ans = max(ans, i + 1)
if idx - l[idx] > 0:
r[idx - l[idx] - 1] = cur
if idx + r[idx] < n - 1:
l[idx + r[idx] + 1] = cur
return ans
arr = [3,5,1,2,4]
m = 3
print(solve(arr, m))输入
[3,5,1,2,4], 3输出结果
4