class Solution {
public:
int longestMountain(vector<int>& arr) {
}
};
845. 数组中的最长山脉
把符合下列属性的数组 arr 称为 山脉数组 ：
arr.length >= 3i（0 < i < arr.length - 1），满足
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]arr[i] > arr[i + 1] > ... > arr[arr.length - 1]给出一个整数数组 arr，返回最长山脉子数组的长度。如果不存在山脉子数组，返回 0 。
示例 1：
输入：arr = [2,1,4,7,3,2,5] 输出：5 解释：最长的山脉子数组是 [1,4,7,3,2]，长度为 5。
示例 2：
输入：arr = [2,2,2] 输出：0 解释：不存在山脉子数组。
提示：
1 <= arr.length <= 1040 <= arr[i] <= 104
进阶：
O(1) 空间解决此问题吗？原站题解
golang 解法, 执行用时: 16 ms, 内存消耗: 6.2 MB, 提交时间: 2023-09-25 15:31:32
// 枚举山顶
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
}
// 枚举山脚
func longestMountain2(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
}
python3 解法, 执行用时: 76 ms, 内存消耗: 17 MB, 提交时间: 2023-09-25 15:30:34
class Solution:
# 枚举山脚
def longestMountain1(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
# 枚举山顶
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
cpp 解法, 执行用时: 16 ms, 内存消耗: 18.4 MB, 提交时间: 2023-09-25 15:27:35
class Solution {
public:
// 枚举山顶
int longestMountain1(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;
}
// 枚举山脚
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;
}
};
java 解法, 执行用时: 2 ms, 内存消耗: 43 MB, 提交时间: 2023-09-25 15:25:54
class Solution {
// 枚举山顶
public int longestMountain(int[] arr) {
int n = arr.length;
if (n == 0) {
return 0;
}
int[] left = new int[n]; // arr[i] 向左侧最多可以扩展的元素数目
for (int i = 1; i < n; ++i) {
left[i] = arr[i - 1] < arr[i] ? left[i - 1] + 1 : 0;
}
int[] right = new int[n]; // arr[i] 向右侧最多可扩展的元素数目
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;
}
// 枚举山脚
public int longestMountain2(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;
}
}