Ming
0%

LeetCode-941

Posted on Edited on In

题目

Snipaste_2020-11-03_10-05-37.png

结果

Snipaste_2020-11-03_10-16-35.png

代码

版本1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public boolean validMountainArray(int[] A) {
        if (A.length < 3) {
            return false;
        }
        for (int i = 1; i < A.length - 1; i++) {
            if (isTop(A, i)) {
                return true;
            }
        }
        return false;
    }

    private boolean isTop(int[] A, int index) {
        if (index == 0 || index == A.length - 1) {
            return false;
        }
        for (int i = 1; i <= index; i++) {
            if (A[i] <= A[i - 1]) {
                return false;
            }
        }
        for (int i = index; i < A.length - 1; i++) {
            if (A[i] <= A[i + 1]) {
                return false;
            }
        }
        return true;
    }
}

版本2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean validMountainArray(int[] A) {
        if (A.length < 3) {
            return false;
        }
        int left = 0, right = A.length - 1;
        for (int i = 1; i < A.length; i++) {
            if (A[i] > A[i - 1]) {
                left++;
            } else {
                break;
            }
        }
        for (int i = A.length - 1; i > 0; i--) {
            if (A[i] < A[i - 1]) {
                right--;
            } else {
                break;
            }
        }
        return left == right && left != 0 && left != A.length - 1;
    }
}

复杂度

版本一

时间复杂度：O（n²）

空间复杂度：O（1）

版本二

时间复杂度：O（n）

空间复杂度：O（1）