[LeetCode] 941. Valid Mountain Array 验证山形数组
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[A.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:
0 <= A.length <= 10000
0 <= A[i] <= 10000?
这道题定义了一种山形数组,长度大于等于3,并且存在一个峰值,左右两边的数字都必须严格递减,不允许有相等的值存在。就是说从开头遍历,一定是严格递增的,直到到达峰值,然后严格递减到末尾,那么可以从开头进行 while 循环,若当前数字小于右边的数字,则i自增1,为了避免溢出,i只能遍历到倒数第二个数字,这样当循环结束的时候,i指向的数字是大于等于右边的数字,是潜在的峰值,当然这里是不能相等的,但此时不需要判断。同样的操作反向来一遍,j从最后一个数字遍历到第二个数字,若当前数字小于其左边的数字时,则j自减1,这样循环结束后,j指向的数字是大于等于左边的数字的,也是潜在的峰值。接下来就要比较这两个峰值是否指向同一个数字,同时i指向的数字不能是第一个,j指向的数字不能是最后一个数字,因为必须要有上坡和下坡的存在,参见代码如下:
class Solution { public: bool validMountainArray(vector<int>& A) { int n = A.size(), i = 0, j = n - 1; while (i < n - 1 && A[i] < A[i + 1]) ++i; while (j > 0 && A[j - 1] > A[j]) --j; return i > 0 && j < n - 1 && i == j; } };
Github 同步地址:
https://github.com/grandyang/leetcode/issues/941
参考资料:
https://leetcode.com/problems/valid-mountain-array/
https://leetcode.com/problems/valid-mountain-array/discuss/194941/C%2B%2B-Track-Peak
https://leetcode.com/problems/valid-mountain-array/discuss/194900/C%2B%2BJavaPython-Climb-Mountain
[LeetCode All in One 题目讲解汇总(持续更新中...)](https://www.cnblogs.com/grandyang/p/4606334.html)
相关推荐
aanndd 2020-08-12
aanndd 2020-07-26
aanndd 2020-07-08
zangdaiyang 2020-07-04
yaohustiAC 2020-06-28
us0 2020-06-28
yaohustiAC 2020-06-28
zangdaiyang 2020-06-28
Clairezz 2020-06-28
嗡汤圆 2020-06-26
嗡汤圆 2020-06-21
aanndd 2020-06-16
aanndd 2020-06-16
码墨 2020-06-16
yaohustiAC 2020-06-11
zangdaiyang 2020-06-10
jiayuqicz 2020-06-09
yaohustiAC 2020-06-06
heray0 2020-06-04