Skip to content

Latest commit

 

History

History
114 lines (98 loc) · 4.26 KB

845. 数组中的最长山脉-Medium.md

File metadata and controls

114 lines (98 loc) · 4.26 KB
Raw

Description

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

Solution

1. 双指针解法

  • 找到“山脉”顶点，即A[i] > A[i-1] and A[i] > A[i+1]，再从这个点往两边延伸计算长度，时间复杂度较优
class Solution:
    def longestMountain(self, A: List[int]) -> int:
        max_len = 0
        for i in range(1, len(A)-1):
            l, r = i, i
            if A[i] > A[i-1] and A[i] > A[i+1]:
                while l-1 >= 0 and A[l] > A[l-1]:
                    l -= 1
                while r + 1 < len(A) and A[r] >A[r+1]:
                    r += 1
                max_len = max(max_len, r-l+1)
        return max_len
  • 枚举山脚：即一个指针固定起始山脚，另一指针固定结束山脚

2. 单调栈解法

  • 题解链接
  • 解题思路：分别以每一个元素作为山顶，求解每一个元素左侧连续小于它的元素个数：left数组，右侧连续小于它的元素个数：right数组。准备好以上的left数组和right数组之后，重新枚举山顶，计算以每个元素作为山顶的山脉的长度。最后返回最大值。
  • 注意单调栈的操作：要先判断清空操作，再判断插入(append)操作
class Solution:
    def longestMountain(self, A: List[int]) -> int:
        n = len(A)
        stack = []
        left, right, res = [0] * n, [0] * n, [0] * n

        for i in range(n):
            if stack and stack[-1] >= A[i]:
                stack = []
            if not stack or stack[-1] < A[i]:
                stack.append(A[i])
            left[i] = len(stack) - 1

        stack = []
        for i in range(n-1, -1, -1):
            if stack and stack[-1] >= A[i]:
                stack = []
            if not stack or stack[-1] < A[i]:
                stack.append(A[i])
            right[i] = len(stack) - 1

        for i in range(n):
            res[i] = left[i]+right[i]  + 1 if left[i] and right[i] else 0
        return max(res) if res else 0

3. 动态规划解法

解题思路（题解）

这种题大致一看就是动态规划。那么动态规划还是三个问题：状态定义、边界条件、递推公式。

  1. 状态定义：这道题应该有三个状态分别是：左山脉、山顶和右山脉。
  2. 边界条件：一般来说边界条件都是在初始值的地方取得，这道题也不例外。
  3. 状态转移：我们用0, 1, 2分别代表左山脉、山顶和右山脉，我们可以得到以下状态转移:
    • 对于状态0：0->0
    • 对于状态1：0->1
    • 对于状态2：1->2, 2->2

个人想法

  • 本质上还是一个遍历找完整山脉（枚举山脚）的做法，效果不如双指针法
class Solution:
    def longestMountain(self, A: List[int]) -> int:
        if not A:
            return 0
        dp = [[0] * len(A) for _ in range(3)]
        dp[0][0] = 1
        for i in range(1, len(A)):
            dp[0][i] = dp[0][i - 1] + 1 if A[i] > A[i - 1] else 1
            dp[1][i] = dp[0][i - 1] + 1 if A[i] > A[i - 1] else 0
            dp[2][i] = max(
                dp[1][i - 1] + 1 if dp[1][i - 1] >= 2 else 0,
				# 2代表处于1状态时，必须前面要有至少2个元素的积累，即形成上升的波段
                dp[2][i - 1] + 1 if dp[2][i - 1] >= 3 else 0
				# 3代表处于2状态时，必须前面要有至少3个元素的积累，即已经具备上升和初步下降的波段【没看懂】
            ) if A[i] < A[i - 1] else 0
        #　print(dp)
        return max(dp[2])