个人中心
gpt4 book ai didi

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

转载 作者：大佬之路 更新时间：2024-01-31 14:16:20 27 4
gpt4 key购买 nike

题目地址：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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

其实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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发

27 4 0
文章推荐： 944. Delete Columns to Make Sorted 删列造序
文章推荐： 910. Smallest Range II 最小差值 II
文章推荐： 937. Reorder Data in Log Files 重新排列日志文件
文章推荐： 913. Cat and Mouse 猫和老鼠
大佬之路
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com