[Swift]LeetCode845.数组中的最长山脉|LongestMountaininArray

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

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

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

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

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

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

Let's call any (contiguous) subarray B (of A) a mountain if the following properties hold:

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

(Note that B could be any subarray of A, including the entire array A.)

Given an array A of integers, return the length of the longest mountain.

Return 0 if there is no mountain.

Example 1:

Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: [2,2,2]
Output: 0
Explanation: There is no mountain.

Note:

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

Follow up:

Can you solve it using only one pass?
Can you solve it in O(1) space?

我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：

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

（注意：B 可以是 A 的任意子数组，包括整个数组 A。）

给出一个整数数组 A，返回最长 “山脉” 的长度。

如果不含有 “山脉” 则返回 0。

示例 1：

输入：[2,1,4,7,3,2,5]
输出：5
解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。

示例 2：

输入：[2,2,2]
输出：0
解释：不含 “山脉”。

提示：

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

156ms

 1 class Solution {
 2     func longestMountain(_ A: [Int]) -> Int {
 3         var longest = 0
 4         var increasing = true
 5         var mountainLength = 0
 6         var hasReturn = false
 7         var i = 0 
 8         while  i < A.count - 1{
 9             if increasing {
10                 if A[i] < A[i+1] {
11                     i += 1
12                     mountainLength += 1
13                 }else if A[i] > A[i+1] {
14                     increasing = false
15                 }else {
16                     i += 1
17                     mountainLength = 0
18                 }
19             }else {
20                 if mountainLength == 0 {
21                      if A[i] >= A[i+1] {
22                         i += 1
23                     }else {
24                          increasing = true
25                     }
26                 }else {
27                     if A[i] > A[i+1] {
28                         hasReturn = true
29                         i += 1
30                         mountainLength += 1
31                     }else {
32                         longest = max(longest, mountainLength + 1)
33                         mountainLength  = 0
34                         increasing = false
35                     }
36                 }
37             }
38         }
39         if hasReturn {
40             return max(longest, mountainLength + 1)
41         }else {
42             return longest
43         }
44     }
45 }

Runtime: 164 ms

Memory Usage: 19.3 MB

 1 class Solution {
 2     func longestMountain(_ A: [Int]) -> Int {
 3         var N:Int = A.count
 4         var res:Int = 0
 5         var up:[Int] = [Int](repeating:0,count:N)
 6         var down:[Int] = [Int](repeating:0,count:N)
 7         for i in stride(from:N - 2,through:0,by:-1)
 8         {
 9             if A[i] > A[i + 1]
10             {
11                 down[i] = down[i + 1] + 1
12             }
13         }
14         for i in 0..<N
15         {
16             if i > 0 && A[i] > A[i - 1]
17             {
18                 up[i] = up[i - 1] + 1
19             }
20             if up[i] > 0 && down[i] > 0
21             {
22                 res = max(res, up[i] + down[i] + 1)
23             }
24         }
25         return res
26     }
27 }

168ms

 1 class Solution {
 2     func longestMountain(_ A: [Int]) -> Int {
 3         if (A.count < 3) {
 4             return 0
 5         }
 6         var l2r = Array(repeating: 0, count: A.count)
 7         var r2l = Array(repeating: 0, count: A.count)
 8         
 9         for i in 1..<A.count {
10             if A[i] > A[i-1] {
11                 l2r[i] = l2r[i-1] + 1
12             }
13         }
14         
15         for i in stride(from: A.count - 2, through: 1, by: -1) {
16             if A[i] > A[i+1] {
17                 r2l[i] = r2l[i+1] + 1
18             }
19         }
20         
21         var result = 0
22         for i in 1..<A.count {
23             if (l2r[i] > 0 && r2l[i] > 0) {
24                 result = max(result, l2r[i] + r2l[i] + 1)
25             }
26         }
27         
28         return result 
29     }
30 }