【LeetCode_941】有效的山脉数组_PythonJava_线性查找解法

输入&＃xff1a;[2,1]
输出&＃xff1a;false

示例 2&＃xff1a;

输入&＃xff1a;[3,5,5]
输出&＃xff1a;false

示例 3&＃xff1a;

输入&＃xff1a;[0,3,2,1]
输出&＃xff1a;true

提示&＃xff1a;

0 <&＃61; A.length <&＃61; 10000
0 <&＃61; A[i] <&＃61; 10000

方法一、暴力求解

我太菜了&＃xff01;&＃xff01;一般最先想到的就是暴力&＃xff0c;而且还没解答出来&＃xff0c;这部分是我的错误之路&＃xff0c;可以跳过直接看方法二。

Python解法

起初打算以i两边的列表是否有序作为判断依据&＃xff08;但是最后证明这个思路也不行&＃xff09;

&＃96;&＃96;&＃96;cpp
class Solution(object):def validMountainArray(self, A):""":type A: List[int]:rtype: bool"""n &＃61; len(A)i &＃61; 1if(n<3):return Falsewhile(i>0 and i<n-1):temp1 &＃61; A[:i&＃43;1]temp2 &＃61; A[i:]if(temp1 &＃61;&＃61; temp1.sort() and temp2.reverse() &＃61;&＃61; temp2.sort()):return Truei &＃61; i&＃43;1return False


但是方法temp1.sort()是一个操作而非返回一个列表&＃xff0c;所以就定义了一堆列表试试。所以改成

class Solution(object):def validMountainArray(self, A):""":type A: List[int]:rtype: bool"""n &＃61; len(A)i &＃61; 1if(n<3):return Falsewhile(i>0 and i<n-1):temp1 &＃61; A[:i&＃43;1]temp2 &＃61; A[i:]l1 &＃61; temp1l2 &＃61; temp2temp1.sort()l3 &＃61; temp1#排序后的temp1temp2.reverse()l4 &＃61; temp2#倒序后的temp2l2.sort()l5 &＃61; l2#排序后的temp2if(l1 &＃61;&＃61; l3 and l4 &＃61;&＃61; l5):return Truei &＃61; i&＃43;1return False


3,5,5 [3,5]和[5,5],右边的列表也是有序的呀…所以这个方法行不通o(╥﹏╥)o

方法二、线性查找i

参考官方解答
思路&＃xff1a; 我们从数组的最左侧开始向右扫描&＃xff0c;直到找到第一个不满足 A[i] A[j &＃43; 1]&＃xff0c;若都满足就返回 true&＃xff0c;否则返回false。

Python解法

class Solution(object):def validMountainArray(self, A):N &＃61; len(A)i &＃61; 0# 递增扫描while i &＃43; 1 < N and A[i] < A[i &＃43; 1]:i &＃43;&＃61; 1# 最高点不能是数组的第一个位置或最后一个位置if i &＃61;&＃61; 0 or i &＃61;&＃61; N - 1:return False# 递减扫描while i &＃43; 1 < N and A[i] > A[i &＃43; 1]:i &＃43;&＃61; 1return i &＃61;&＃61; N - 1#走到最后则符合要求&＃xff0c;中途停下来了则返回False

Java解法

class Solution {public boolean validMountainArray(int[] A) {int N &＃61; A.length;int i &＃61; 0;// 递增扫描while (i &＃43; 1 < N && A[i] < A[i &＃43; 1]) {i&＃43;&＃43;;}// 最高点不能是数组的第一个位置或最后一个位置if (i &＃61;&＃61; 0 || i &＃61;&＃61; N - 1) {return false;}// 递减扫描while (i &＃43; 1 < N && A[i] > A[i &＃43; 1]) {i&＃43;&＃43;;}return i &＃61;&＃61; N - 1;}
}


复杂度分析

时间复杂度&＃xff1a;O(N)
空间复杂度&＃xff1a;O(1)

博主比较小白&＃xff0c;但是热爱分享。一直感觉自己写代码的能力&＃xff0c;算法能力都不太行&＃xff0c;所以最近开始刷LeetCode&＃xff0c;一方面记录方便自己学习&＃xff0c;另一方面给需要的同伴参考。虽然失败并不可怕&＃xff0c;但是也希望同伴们少踩一些坑。分析算法挺费劲的&＃xff0c;留个赞或评论支持一下博主吧&＃xff01;同时我也非常希望写出更通俗易懂的文章&＃xff0c;知识尚浅&＃xff0c;如有遗漏或错误&＃xff0c;欢迎指正~