子數組的取值範圍

Description

給定數組arr和整數num，求arr的連續子數組中滿足：其最大值減去最小值的結果大于num的個數。請實作一個時間複雜度為O(length(arr))的算法。

Input

輸入第一行為測試用例個數。每一個用例有若幹行，第一行為數組，每一個數用空格隔開，第二行為num。

Output

輸出一個值。

Sample Input 1

1

3 6 4 3 2

2

Sample Output 1

6

使用兩個連結清單，o(n^2)的話會逾時，C++一直wrong answer

def compare(nlist, number):
    if (len(nlist) == 1):
        return "false"
    else:
        max = nlist[0]
        min = nlist[0]
        for n in nlist:
            if (n > max):
                max = n
            if (n < min):
                min = n
        if (max - min > number):
            return "true"
        else:
            return "false"

if __name__ == "__main__":
    n = int(input())
    for k in range(n):
        arr = input()
        nlist = [int(n) for n in arr.split()]
        number = input()
        number = int(number)
        count = 0
        lenth = len(nlist)
        for i in range(lenth):
            for j in range(i, lenth):
                temp = compare(nlist[i:j + 1], number)
                if (temp == "true"):
                    count = count + 1
        print(count)