845-数组中的最长山脉(Longest Mountain in Array)
发表于：2021-12-03 | 分类： 中等
字数统计: 2.7k | 阅读时长: 13分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/longest-mountain-in-array

英文原文

You may recall that an array arr is a mountain array if and only if:

  • arr.length >= 3
  • There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
    • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
    • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.

 

Example 1:

Input: arr = [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: arr = [2,2,2]
Output: 0
Explanation: There is no mountain.

 

Constraints:

  • 1 <= arr.length <= 104
  • 0 <= arr[i] <= 104

 

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
解释：不含 “山脉”。

 

提示：

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

通过代码

高赞题解

方法一：枚举山顶

思路与算法

对于一座「山脉」，我们称首元素 $B[0]$ 和尾元素 $B[\text{len}(B)-1]$ 为「山脚」，满足题目要求 $B[i-1] < B[i] > B[i+1]$ 的元素 $B[i]$ 为「山顶」。为了找出数组 $\textit{arr}$ 中最长的山脉，我们可以考虑枚举山顶，再从山顶向左右两侧扩展找到山脚。

由于从左侧山脚到山顶的序列是严格单调递增的，而从山顶到右侧山脚的序列是严格单调递减的，因此我们可以使用动态规划（也可以理解为递推）的方法，计算出从任意一个元素开始，向左右两侧最多可以扩展的元素数目。

我们用 $\textit{left}[i]$ 表示 $\textit{arr}[i]$ 向左侧最多可以扩展的元素数目。如果 $\textit{arr}[i-1] < \textit{arr}[i]$，那么 $\textit{arr}[i]$ 可以向左扩展到 $\textit{arr}[i-1]$，再扩展 $\textit{left}[i]$ 个元素，因此有

$$
\textit{left}[i] = \textit{left}[i-1] + 1
$$

如果 $\textit{arr}[i-1] \geq \textit{arr}[i]$，那么 $\textit{arr}[i]$ 无法向左扩展，因此有

$$
\textit{left}[i] = 0
$$

特别地，当 $i=0$ 时，$\textit{arr}[i]$ 为首元素，无法向左扩展，因此同样有

$$
\textit{left}[0] = 0
$$

同理，我们用 $\textit{right}[i]$ 表示 $\textit{arr}[i]$ 向右侧最多可以扩展的元素数目，那么有类似的状态转移方程（递推式）

$$
\textit{right}[i] = \begin{cases}
\textit{right}[i+1]+1, & \textit{arr}[i] > \textit{arr}[i+1] \
0, & \textit{arr}[i] \leq \textit{arr}[i+1] 或 i=n-1
\end{cases}
$$

其中 $n$ 是数组 $\textit{arr}$ 的长度。

在计算出所有的 $\textit{left}$ 以及 $\textit{right}$ 之后，我们就可以枚举山顶。需要注意的是，只有当 $\textit{left}[i]$ 和 $\textit{right}[i]$ 均大于 $0$ 时，$\textit{arr}[i]$ 才能作为山顶，并且山脉的长度为 $\textit{left}+\textit{right}[i]+1$。

在所有的山脉中，最长的即为答案。

代码

[sol1-C++]
class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size();
        if (!n) {
            return 0;
        }
        vector<int> left(n);
        for (int i = 1; i < n; ++i) {
            left[i] = (arr[i - 1] < arr[i] ? left[i - 1] + 1 : 0);
        }
        vector<int> right(n);
        for (int i = n - 2; i >= 0; --i) {
            right[i] = (arr[i + 1] < arr[i] ? right[i + 1] + 1 : 0);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (left[i] > 0 && right[i] > 0) {
                ans = max(ans, left[i] + right[i] + 1);
            }
        }
        return ans;
    }
};
[sol1-Java]
class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        if (n == 0) {
            return 0;
        }
        int[] left = new int[n];
        for (int i = 1; i < n; ++i) {
            left[i] = arr[i - 1] < arr[i] ? left[i - 1] + 1 : 0;
        }
        int[] right = new int[n];
        for (int i = n - 2; i >= 0; --i) {
            right[i] = arr[i + 1] < arr[i] ? right[i + 1] + 1 : 0;
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (left[i] > 0 && right[i] > 0) {
                ans = Math.max(ans, left[i] + right[i] + 1);
            }
        }
        return ans;
    }
}
[sol1-Python3]
class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        if not arr:
            return 0
            
        n = len(arr)
        left = [0] * n
        for i in range(1, n):
            left[i] = (left[i - 1] + 1 if arr[i - 1] < arr[i] else 0)
        
        right = [0] * n
        for i in range(n - 2, -1, -1):
            right[i] = (right[i + 1] + 1 if arr[i + 1] < arr[i] else 0)
        
        ans = 0
        for i in range(n):
            if left[i] > 0 and right[i] > 0:
                ans = max(ans, left[i] + right[i] + 1)
        
        return ans
[sol1-Golang]
func longestMountain(arr []int) int {
    n := len(arr)
    left := make([]int, n)
    for i := 1; i < n; i++ {
        if arr[i-1] < arr[i] {
            left[i] = left[i-1] + 1
        }
    }
    right := make([]int, n)
    for i := n - 2; i >= 0; i-- {
        if arr[i+1] < arr[i] {
            right[i] = right[i+1] + 1
        }
    }
    ans := 0
    for i, l := range left {
        r := right[i]
        if l > 0 && r > 0 && l+r+1 > ans {
            ans = l + r + 1
        }
    }
    return ans
}
[sol1-C]
int longestMountain(int* arr, int arrSize) {
    if (!arrSize) {
        return 0;
    }
    int left[arrSize];
    left[0] = 0;
    for (int i = 1; i < arrSize; ++i) {
        left[i] = (arr[i - 1] < arr[i] ? left[i - 1] + 1 : 0);
    }
    int right[arrSize];
    right[arrSize - 1] = 0;
    for (int i = arrSize - 2; i >= 0; --i) {
        right[i] = (arr[i + 1] < arr[i] ? right[i + 1] + 1 : 0);
    }

    int ans = 0;
    for (int i = 0; i < arrSize; ++i) {
        if (left[i] > 0 && right[i] > 0) {
            ans = fmax(ans, left[i] + right[i] + 1);
        }
    }
    return ans;
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{arr}$ 的长度。

  • 空间复杂度：$O(n)$，即为数组 $\textit{left}$ 和 $\textit{right}$ 需要使用的空间。

方法二：枚举山脚

思路与算法

我们也可以枚举山脚。例如当我们从左向右遍历整个数组 $\textit{arr}$ 时，可以使用双指针的方法，一个指针枚举左侧山脚，另一个指针不断向右移动到右侧山脚。

具体地，我们使用指针 $\textit{left}$ 指向左侧山脚，它的初始值为 $0$。每次当我们固定 $\textit{left}$ 时：

  • 我们首先需要保证 $\textit{left} + 2 < n$，这是因为山脉的长度至少为 $3$；其次我们需要保证 $\textit{arr}[\textit{left}] < \textit{arr}[\textit{left} + 1]$，否则 $\textit{left}$ 对应的不可能时左侧山脚；

  • 我们将右侧山脚的 $\textit{right}$ 的初始值置为 $\textit{left}+1$，随后不断地向右移动 $\textit{right}$，直到不满足 $\textit{arr}[\textit{right}] < \textit{arr}[\textit{right} + 1]$ 为止，此时：

    • 如果 $\textit{right} = n-1$，说明我们已经移动到了数组末尾，已经无法形成山脉了；

    • 否则，$\textit{right}$ 指向的可能是山顶。我们需要额外判断是有满足 $\textit{arr}[\textit{right}] > \textit{arr}[\textit{right} + 1]$，这是因为如果两者相等，那么 $\textit{right}$ 指向的就不是山顶了。

  • 如果 $\textit{right}$ 指向的确实是山顶，那么我们使用类似的方法，不断地向右移动 $\textit{right}$，直到不满足 $\textit{arr}[\textit{right}] > \textit{arr}[\textit{right} + 1]$ 为止，此时，$\textit{right}$ 指向右侧山脚，$\textit{arr}[\textit{left}]$ 到 $\textit{arr}[\textit{right}]$ 就对应着一座山脉；

  • 需要注意的是，右侧山脚有可能是下一个左侧山脚，因此我们需要将 $\textit{right}$ 的值赋予 $\textit{left}$，以便与进行下一次枚举。在其它所有不满足要求的情况下，$\textit{right}$ 对应的位置都不可能是下一个左侧山脚，因此可以将 $\textit{right} + 1$ 的值赋予 $\textit{left}$。

在下面的代码中，当不满足要求时，我们立即将 $\textit{right}$ 的值加 $1$。这样一来，我们就可以统一在下一次枚举左侧山脚之前，将 $\textit{right}$ 的值赋予 $\textit{left}$ 了。

代码

[sol2-C++]
class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size();
        int ans = 0;
        int left = 0;
        while (left + 2 < n) {
            int right = left + 1;
            if (arr[left] < arr[left + 1]) {
                while (right + 1 < n && arr[right] < arr[right + 1]) {
                    ++right;
                }
                if (right < n - 1 && arr[right] > arr[right + 1]) {
                    while (right + 1 < n && arr[right] > arr[right + 1]) {
                        ++right;
                    }
                    ans = max(ans, right - left + 1);
                }
                else {
                    ++right;
                }
            }
            left = right;
        }
        return ans;
    }
};
[sol2-Java]
class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        int ans = 0;
        int left = 0;
        while (left + 2 < n) {
            int right = left + 1;
            if (arr[left] < arr[left + 1]) {
                while (right + 1 < n && arr[right] < arr[right + 1]) {
                    ++right;
                }
                if (right < n - 1 && arr[right] > arr[right + 1]) {
                    while (right + 1 < n && arr[right] > arr[right + 1]) {
                        ++right;
                    }
                    ans = Math.max(ans, right - left + 1);
                } else {
                    ++right;
                }
            }
            left = right;
        }
        return ans;
    }
}
[sol2-Python3]
class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        ans = left = 0
        while left + 2 < n:
            right = left + 1
            if arr[left] < arr[left + 1]:
                while right + 1 < n and arr[right] < arr[right + 1]:
                    right += 1
                if right < n - 1 and arr[right] > arr[right + 1]:
                    while right + 1 < n and arr[right] > arr[right + 1]:
                        right += 1
                    ans = max(ans, right - left + 1)
                else:
                    right += 1
            left = right
        return ans
[sol2-Golang]
func longestMountain(arr []int) int {
    n := len(arr)
    ans := 0
    left := 0
    for left+2 < n {
        right := left + 1
        if arr[left] < arr[left+1] {
            for right+1 < n && arr[right] < arr[right+1] {
                right++
            }
            if right < n-1 && arr[right] > arr[right+1] {
                for right+1 < n && arr[right] > arr[right+1] {
                    right++
                }
                if right-left+1 > ans {
                    ans = right - left + 1
                }
            } else {
                right++
            }
        }
        left = right
    }
    return ans
}
[sol2-C]
int longestMountain(int* arr, int arrSize) {
    int ans = 0;
    int left = 0;
    while (left + 2 < arrSize) {
        int right = left + 1;
        if (arr[left] < arr[left + 1]) {
            while (right + 1 < arrSize && arr[right] < arr[right + 1]) {
                ++right;
            }
            if (right < arrSize - 1 && arr[right] > arr[right + 1]) {
                while (right + 1 < arrSize && arr[right] > arr[right + 1]) {
                    ++right;
                }
                ans = fmax(ans, right - left + 1);
            } else {
                ++right;
            }
        }
        left = right;
    }
    return ans;
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{arr}$ 的长度。

  • 空间复杂度：$O(1)$。

统计信息

通过次数 提交次数 AC比率
38716 91782 42.2%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
动态规划 数组 双指针 枚举
上一篇:
843-猜猜这个单词(Guess the Word)
下一篇:
844-比较含退格的字符串(Backspace String Compare)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo