Leetcode 845 Longest Mountain in Array

发表于 |

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

分析：
在一个数组中找最长的先严格上升后严格下降的连续序列，注意A.length达到10000，n^2方法显然不行

思路：
直接遍历一遍，找到一个上升点然后开始遍历，处理一些小情况即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution(object):
    def longestMountain(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        # O(n) time, O(1) space
        i,n = 0,len(A)
        res = 0
        while i < n-1:
        	#找到一个上升点
            if A[i] < A[i+1]:
            	# 先找上升序列
                j = i+1
                while j < n and A[j] > A[j-1]: j += 1
                # 如若遍历到数组末尾直接返回结果
                if j == n: return res
                # 这个判断语句处理[1,2,2,0]这种情况
                if A[j] != A[j-1]: 
                    while j < n and A[j] < A[j-1]: j += 1
                    res = max(res,j-i)
                    i = j-2
                else:
                    i = j-1
            i += 1
        return res

O(n) time, O(1) space
72 / 72 test cases passed.
difficulty: medium
Runtime: 73 ms