941. Valid Mountain Array 有效的山脉数组

作者： 负雪明烛 id： fuxuemingzhu 个人博客： http://fuxuemingzhu.cn/

---

@TOC

题目地址：https://leetcode.com/problems/valid-mountain-array/description/

题目描述

Given an array A of integers, return true if and only if it is a valid mountain array.

Recall that A is a mountain array if and only if:

• A.length >= 3
• There exists some i with 0 < i < A.length - 1 such that:
  • A[0] < A[1] < ... A[i-1] < A[i]
  • A[i] > A[i+1] > ... > A[B.length - 1]

Example 1:

Input: [2,1]
Output: false

Example 2:

Input: [3,5,5]
Output: false

Example 3:

Input: [0,3,2,1]
Output: true

Note:

1. 0 <= A.length <= 10000
2. 0 <= A[i] <= 10000

题目大意

判断一个数组是不是山形数组，山形数组最少有3个数字，中间有个最大的数字，往两边都是依次减小的。

解题方法

方法很直接，先判断是不是依次增加，然后再判断是不是依次减小，如果整个数组都是这样的就是山形数组了。

所以有两个while循环，一个是向后查找更大的数字，第二个是向后找最小的数字。在第一个while结束的时候，找到的元素的位置应该在数组中间，而第二个while结束之后，元素的位置应该在数组的结尾。

时间复杂度是O(N)，空间复杂度是O(1)。

class Solution:
    def validMountainArray(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        N = len(A)
        if N < 3:
            return False
        i = 0
        while i < N - 1:
            if A[i] < A[i + 1]:
                i += 1
            else:
                break
        if i == 0 or i == N - 1: return False
        while i < N - 1:
            if A[i] > A[i + 1]:
                i += 1
            else:
                break
        return i == N - 1

其实while的条件也可以使用判断语句，这样的话，我们就直接停止。

class Solution(object):
    def validMountainArray(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        print(A)
        N = len(A)
        if N < 3: return False
        i = 0
        while i < N - 1 and A[i + 1] > A[i]:
            i += 1
        if i == 0 or i == N - 1: return False
        while i < N - 1 and A[i] > A[i + 1]:
            i += 1
        return i == N - 1

日期

2018 年 11 月 18 日 —— 出去玩了一天，腿都要废了 2018 年 11 月 24 日 —— 周六快乐