047-力扣刷题-845--数组中的最长山脉

我们把数组 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

 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution(object):
    def longestMountain(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        if len(A) < 3:
            return 0
        ret = 0

        # 从第一个数开始判断
        stack = [0]

        # 能找到的最长山脉，当只有01012之类的出现时可以尽早结束循环
        max_num = 2 *(max(A)-min(A)) + 1

        # 开始循环查找
        while stack:
            cur = stack.pop()

            # 当已经找到最长山脉时直接结束循环
            if ret >= len(A) - cur or ret >= max_num: #当前山峰的长度已经比后面可能的长度大
                break

            # 山脉左右两边元素个数
            l_tmp, r_tmp = 0, 0

            # 从cur位置开始查找
            while cur < len(A) - 1:
                if A[cur] < A[cur+1] and r_tmp == 0:
                    l_tmp += 1
                    cur += 1
                elif A[cur] > A[cur+1] and l_tmp > 0:
                    r_tmp += 1
                    cur += 1
                else:
                    break

            # 查找完成后判断是不是找到更长的
            if r_tmp>0 and l_tmp+r_tmp>=ret:
                ret = l_tmp+r_tmp+1

            # 当没找到时应该从下一个位置继续寻找
            if r_tmp == 0:
                cur += 1

            # 这里主要是把下一个查找位置压入栈中，注意当找到山脉时只需把当前没构成山脉的位置添加过去即可
            if cur < len(A):
                stack.append(cur)
        return ret

拼多多的最长山谷

 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
A=[1,2,3,2,5,6,5,3,2,3,4,8,1]
def longestMountain(A):
    """
    :type A: List[int]
    :rtype: int
    """
    if len(A) < 3:
        return 0
    ret = 0

    # 从第一个数开始判断
    stack = [0]

    # 能找到的最长山脉，当只有101012之类的出现时可以尽早结束循环
    max_num = 2 *(max(A)-min(A)) + 1

    # 开始循环查找
    while stack:
        cur = stack.pop()

        # 当已经找到最长山谷时直接结束循环
        if ret >= len(A) - cur or ret >= max_num:
            break

        # 山谷左右两边元素个数
        l_tmp, r_tmp = 0, 0

        # 从cur位置开始查找
        while cur < len(A) - 1:
            if A[cur] > A[cur+1] and r_tmp == 0:
                l_tmp += 1
                cur += 1
            elif A[cur] < A[cur+1] and l_tmp > 0:
                r_tmp += 1
                cur += 1
            else:
                break

        # 查找完成后判断是不是找到更长的
        if r_tmp>0 and l_tmp+r_tmp>=ret:
            ret = l_tmp+r_tmp+1

        # 当没找到时应该从下一个位置继续寻找
        if r_tmp == 0:
            cur += 1

        # 这里主要是把下一个查找位置压入栈中，注意当找到山脉时只需把当前没构成山脉的位置添加过去即可
        if cur < len(A):
            stack.append(cur)
    return ret

另一种最长山谷的求法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
x=[1,2,5,3,2,3,4]
n = len(x)

if n < 3:
    print (0)
else:
    res = 0
    for i in range(1,n-1):
        l = i
        while l > 0 and x[l-1]>x[l]:
            l -= 1
        r = i
        while r < n-1 and x[r+1]>x[r]:
            r += 1
        if l < i and r > i:
            res = max(res,r-l+1)
    print (res if res >= 3 else 0)

输出

1
2
xx=input()#输入一行
x=list(map(int,xx.split(' ')))  #注意不要多输入了空格