关于阵列内最深坑的困惑

Question

我把这个问题作为面试的先决条件，

给出了一个由N个整数组成的非空零索引数组A.该阵列中的pit是整数(P，Q，R)的任意三重子，使得0≤P序列[ AP，AP+1，.，AQ]严格递减，即AP> AP+1 >.> AQ； 序列AQ，AQ+1，.，AR严格增加，即AQ < AQ+1 <.< AR。 坑的深度(P，Q，R)是数min{AP−AQ，AR−AQ}。例如，考虑由10个元素组成的数组A，这样： A=0 A1 =1 A2 =3 A3 = -2 A4 =0 A5 =1 A6 =0 A7 = -3 A8 =2 A9 =3 由于序列[A2，A3]严格减少(3 >−2)，序列[A3，A4]严格增加(−2 < 0)，因此三重态(2，3，4)是该阵列中的一个坑。深度为min{A2−A3，A4−A3} = 2。 三重奏(2，3，5)是另一个深3的坑。 三重奏(5，7，8)是另一个深4的坑。这个阵列中没有比4深的坑(即深度大于4)。

它说三重奏(5，7，8)的深坑深度为4。

但三重奏(2，7，9)不是有最深的坑深6吗？

Triplet (2，7，9)的对应值是(3，-3，3)，它也满足上述条件，即

1) 0 ≤ P < Q < R < N
2) A[P] > A[P+1] > ... > A[Q] and A[Q] < A[Q+1] < ... < A[R]

所以在这个例子中，min{AP−AQ，AR−AQ}是6。

我在这里错过了什么？

P.S.，如果你认为这篇文章不属于这个论坛，那么请指出我应该把它放在哪里。

Answer 1

请参见从P到Q的2 to 7序列。

是3 -2 0 1 0 -3。

序列[ AP，AP+1，.，AQ]严格递减，即AP> AP+1 >.> AQ；

规则说，这应该是一个递减的顺序。但不是3>-2，而是-2 is not greater than 0。在这里，序列中断.

来自7 to 9。没有问题，因为序列在增加。-3<2<3。

Answer 2

对最深坑问题的迅速回答：

 func solution(_ array: [Int]) -> Int {

        //guaranty we have at least three elements
        if array.isEmpty  {
            print("isEmpty")
            return -1
        }

        if array.count < 3 {
            print("is less than 3")
            return -1
        }

        //extremum point; max or min points
        var extremumPoints = [Int]()

        //adding first element
        extremumPoints.append(array[0])

        //calculate extremum points for 1 to one before last element
        for i in 1..<(array.count - 1) {

            let isRelativeExtremum = ((array[i] - array[i - 1]) * (array[i] - array[i + 1])) > 0
            //we call a point semi-extremum if a point is equal to previous element or next element and not equal to previous element or next element
            let isSemiExtremum = ((array[i] != array[i - 1]) && (array[i] == array[i + 1])) || ((array[i] != array[i + 1]) && (array[i] == array[i - 1]))

            if isRelativeExtremum || isSemiExtremum {
                extremumPoints.append(array[i])
            }
        }

        //adding last element
        extremumPoints.append(array[array.count - 1])

        //we will hold depthes in this array
        var depthes = [Int]()

        for i in 1..<(extremumPoints.count - 1) {

            let isBottomOfaPit = extremumPoints[i] < extremumPoints[i - 1] && extremumPoints[i] < extremumPoints[i + 1]

            if isBottomOfaPit {

                let d1 = extremumPoints[i - 1] - extremumPoints[i]
                let d2 = extremumPoints[i + 1] - extremumPoints[i]
                let d = min(d1, d2)
                depthes.append(d)
            }

        }

        //deepest pit
        let deepestPit = depthes.max()
        return deepestPit ?? -1
    }

//*

let A = [0,1,3,-2,0,1,0,-3,2,3]
let deepestPit = solution(A)
print(deepestPit) // 4

Answer 3

def deepest(A):     
    def check(p, q, r, A):
        if A[p] > A[q] and A[q] < A[r]:
            return min(A[p] - A[q], A[r] - A[q])
        else:
            return -1
    max_depth = 0
    for i in range(1, len(A) - 2):
        if A[i-1] > A[i] < A[i + 1]:
            p = i
            r = i
            while 0 <= p and r <= len(A) - 1:
                depth = check(p, i, r, A)
                max_depth = max(max_depth, depth)
                p -= 1
                r += 1
    return max_depth