问题是从给定列表中查找不包含大于指定上限数字的子列表总数right并且子列表的最大数量应该大于下限left假设我的清单是：x=[2, 0, 11, 3, 0]子列表元素的上限是10下界是1那么我的子列表可以是[[2],[2,0],[3],[3,0]]因为子列表始终是连续的。我的脚本运行良好并产生正确的输出，但需要一些优化

def query(sliced,left,right):
    end_index=0
    count=0
    leng=len(sliced)
    for i in range(leng):
        stack=[]
        end_index=i

        while(end_index<leng and sliced[end_index]<=right):

            stack.append(sliced[end_index])
            if max(stack)>=left:
                count+=1
            end_index+=1

    print (count)

origin=[2,0,11,3,0]
left=1
right=10
query(origin,left,right)

output:4

对于一个列表说x=[2,0,0,1,11,14,3,5]有效的子列表可以是[[2],[2,0],[2,0,0],[2,0,0,1],[0,0,1],[0,1],[1],[3],[5],[3,5]]总数为 10

暴力破解

生成每个可能的子列表并检查给定的条件是否适用于每个子列表。

最坏的情况：对于每个元素e在数组中，left < e < right。 时间复杂度：O(n^3)

优化的暴力破解（OP的代码）

对于数组中的每个索引，增量构建一个有效的临时列表（尽管实际上并不需要）。

最坏的情况：对于每个元素e在数组中，left < e < right。 时间复杂度：O(n^2)

更优化的解决方案

如果数组有n元素，则数组中子列表的数量为1 + 2 + 3 + ... + n = (n * (n + 1)) / 2 = O(n^2)。我们可以战略性地使用这个公式。

首先，正如@Tim提到的，我们可以只考虑不包含任何大于的数字的子列表的总和right通过对列表中大于的数字进行分区right。这将任务减少为仅考虑所有元素小于或等于的子列表right然后总结答案。

接下来，通过关于大于或等于的数字对缩减子列表进行分区来分解缩减子列表（是的，子列表的子列表）left。对于每个子列表，计算该子列表的子列表的可能子列表的数量（即k * (k + 1) / 2如果子列表有长度k）。一旦完成所有子列表的子列表，将它们添加在一起（将它们存储在，比如说，w）然后计算该子列表的可能子列表的数量并减去w.

然后按总和汇总结果。

最坏的情况：对于每个元素e在数组中，e < left.

时间复杂度：O(n)

我知道这很难理解，所以我包含了工作代码：

def compute(sliced, lo, hi, left):
    num_invalid = 0
    start = 0
    search_for_start = True
    for end in range(lo, hi):
        if search_for_start and sliced[end] < left:
            start = end
            search_for_start = False
        elif not search_for_start and sliced[end] >= left:
            num_invalid += (end - start) * (end - start + 1) // 2
            search_for_start = True
    if not search_for_start:
        num_invalid += (hi - start) * (hi - start + 1) // 2
    return ((hi - lo) * (hi - lo + 1)) // 2 - num_invalid

def query(sliced, left, right):
    ans = 0
    start = 0
    search_for_start = True
    for end in range(len(sliced)):
        if search_for_start and sliced[end] <= right:
            start = end
            search_for_start = False
        elif not search_for_start and sliced[end] > right:
            ans += compute(sliced, start, end, left)
            search_for_start = True
    if not search_for_start:
        ans += compute(sliced, start, len(sliced), left)
    return ans