有效山阵

Question

我想知道是否有一种编程方法来确定数组是否具有完美的山脉图案，没有山谷。（图中示例）

来源：https://leetcode.com/problems/valid-mountain-array/

编辑：

我在 C 中的尝试：

#include<stdio.h>

int AscOrDes(int a[], int first, int last)
{
    int i;
    for(i=first; i<last; i++)
    {
        if(a[i]>a[i+1])
            return(1);
        else if(a[i]<a[i+1])
            return(2);
    }
    return 0;
}

int main() {
    int a[1000],n,i,big=0,r1,r2;
    scanf("%d",&n);
    for(i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=0; i<n; i++)
    {
        if(a[i]>=a[big])
            big=i;
    }
    r1=AscOrDes(a, 0, big);
    r2=AscOrDes(a, big, n);
    if(r1==2 && r2==1 && big!=0 && big!=n-1)
        printf("True");
    else
        printf("False");
    return 0;
}

上面的代码不适用于以下输入：

8
1 3 2 5 4 3 2 0

它给出输出：

True

虽然它并不是一个完美的山阵。

我在程序中所做的是检查哪个元素是最大的（big），并检查最大元素左侧的元素是否按升序排列，右侧的元素是否按降序排列（山应该是怎样的） ）。

Answer 1

将尝试这种方式：

def is_moutain(A):
    i = 1

    N = len(A)
    
    while i < N and A[i] > A[i-1]:   # go on if ascending, and more items existing 
        i += 1
        
    if i == 1 or i == N:
        return False
    
       
    while N > i and A[i] < A[i-1]:   # at the descending point...
        i += 1

    return i == N
 
if __name__ == '__main__':

    print(is_moutain([0, 2, 3, 4, 5, 3, 1]))    # True
    print(is_moutain([0, 2, 3, 4, 5, 2, 4]))    # False 

Answer 2

这是一个使用以下方法的 Python 解决方案itertools.groupby：

import itertools

def is_mountain(arr):
    return [u for u, _ in itertools.groupby(
        (b - a for a, b in zip(arr, arr[1:])),  # slope as difference
        lambda v: v // abs(v) if v else v       # slope as unit vector
    )] == [1, -1]  # strictly increasing, then decreasing

print(is_mountain([0, 2, 3, 4, 5, 2, 1, 0]))  # True
print(is_mountain([0, 2, 3, 3, 5, 2, 1, 0]))  # False

给定示例输入：

[0, 2, 3, 3, 5, 2, 1, 0]

第一个生成器 ( b - a for a, b in zip(...)) 减去每对相邻元素以生成一系列高程变化（各个坡度）：

[2, 1, 0, 2, -3, -1, -1]

v // abs(v) lambda用作参数的表达式通过将每个除以其大小来对它们key进行itertools.groupby标准化，生成一系列单位向量（1 表示增加，-1 表示减少）：

[1, 1, 0, 1, -1, -1, -1]

itertools.groupby组合相同的相邻元素，产生：

[1, 0, 1, -1]

然后，我们可以简单地将“山”定义为一个列表，通过上述过程会产生准确的结果[1, -1]（所有增加后都会减少）。