[Swift]LeetCode852.山脉数组的峰顶索引|PeakIndexinaMountainArray

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10589081.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Let's call an array A a mountain if the following properties hold:

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

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

Example 1:

Input: [0,1,0]
Output: 1

Example 2:

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

Note:

3 <= A.length <= 10000
0 <= A[i] <= 10^6
A is a mountain, as defined above.

我们把符合下列属性的数组 A 称作山脉：

A.length >= 3
存在 0 < i < A.length - 1 使得A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

给定一个确定为山脉的数组，返回任何满足 A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] 的 i 的值。

示例 1：

输入：[0,1,0]
输出：1

示例 2：

输入：[0,2,1,0]
输出：1

提示：

3 <= A.length <= 10000
0 <= A[i] <= 10^6
A 是如上定义的山脉

20ms

 1 class Solution {
 2     func peakIndexInMountainArray(_ A: [Int]) -> Int {
 3         var peak = 0
 4         for i in 1..<A.count {
 5             if A[i - 1] < A[i] {
 6                 peak = i
 7             }
 8         }        
 9         return peak
10     }
11 }

20ms

 1 class Solution {
 2         func peakIndexInMountainArray(_ A: [Int]) -> Int {
 3         return mountain(0, A.count-1, A)
 4     }
 5 
 6     func mountain(_ from:Int,_ to:Int,_ A: [Int]) -> Int{
 7         if from == to{ return to }
 8         if from == to - 1 { return A[from]>A[to] ? from : to }
 9         let mid = (from + to)/2
10         if A[mid-1] < A[mid] && A[mid] > A[mid+1]{
11             return mid
12         }
13         if A[mid] < A[mid+1] {
14             return mountain(mid,to,A)
15         }else{
16             return mountain(from,mid,A)
17         }
18     }
19 }

24ms

 1 class Solution {
 2     func peakIndexInMountainArray(_ A: [Int]) -> Int {
 3         var temp = 0
 4         
 5         for (index, _) in A.enumerated() {
 6             let aValue = A[index]
 7             let bValue = A[index+1]
 8             if aValue > bValue{
 9                 temp = index
10                 break
11             }
12         }
13         return temp
14     }
15 }

28ms

 1 class Solution {
 2     func peakIndexInMountainArray(_ A: [Int]) -> Int {
 3         var left = 0, right = A.count - 1
 4     var mid = (left + right) / 2
 5     
 6     while !(A[mid] > A[mid - 1] && A[mid] > A[mid + 1]) {
 7         if (A[mid] < A[mid - 1]) {
 8             right = right - 1
 9         } else {
10             left = left + 1
11         }
12         mid = (left + right) / 2
13     }
14     
15     return mid
16     }
17 }

32ms

 1 class Solution {
 2         func peakIndexInMountainArray(_ A: [Int]) -> Int {
 3         return mountain(0, A.count-1, A)
 4     }
 5 
 6     func mountain(_ from:Int,_ to:Int,_ A: [Int]) -> Int{
 7         if to - from < 2 {
 8             if from == to{
 9                 return to
10             }
11             if from == to - 1 {
12                 return A[from]>A[to] ? from : to
13             }
14         }
15         let mid = (from + to)/2
16         if A[mid-1] < A[mid] && A[mid] > A[mid+1]{
17             return mid
18         }
19         if A[mid] < A[mid+1] {
20             return mountain(mid,to,A)
21         }else{
22             return mountain(from,mid,A)
23         }
24     }
25 }

84ms

 1 class Solution {
 2     func peakIndexInMountainArray(_ A: [Int]) -> Int {
 3         var right = A.count - 1
 4         var left = 0
 5         while true  {
 6             var middle = (right + left) / 2
 7             let moreThanLast = A[middle] > A[middle - 1]
 8             let moreThanNext =  A[middle] > A[middle + 1]
 9             if moreThanLast && moreThanNext {
10                 return middle
11             }
12             if moreThanLast && !moreThanNext {
13                 left = middle
14             }
15             if !moreThanLast && moreThanNext {
16                 right =  middle
17             }
18         }
19     }
20 }

88ms

 1 class Solution {
 2     func peakIndexInMountainArray(_ A: [Int]) -> Int {
 3         for i in 1...A.count-2 {
 4             let ai = A[i]
 5             let ai_1 = A[i-1]
 6             let ai1 = A[i+1]
 7             if ai > ai_1 && ai > ai1 {
 8                 return i;
 9             }
10         }
11         return 0;
12     }
13 }

96ms

 1 class Solution {
 2     func peakIndexInMountainArray(_ A: [Int]) -> Int {
 3         for i in 0..<A.count - 1 {
 4             if A[i] > A[i+1] {
 5                 return i
 6             }
 7         }
 8         
 9         return -1
10     }
11 }

132 ms

 1 class Solution {
 2     func peakIndexInMountainArray(_ A: [Int]) -> Int {
 3         var result = 0
 4     var climbing = true
 5     if A.count < 3 {
 6         return result
 7     }
 8     for i in 1..<A.count {
 9         if climbing {
10             if A[i-1] < A[i] && A[i] > result {
11                 result = i
12             } else if A[i-1] >= A[i] {
13                 climbing = false
14             }
15         } else {
16             if A[i-1] < A[i] {
17                 result = -1
18             }
19         }
20     }
21     return result
22     }
23 }