845. 数组中的最长山脉

中等动态规划左右两遍预处理上坡下坡长度力扣原题 ↗

题目描述

若数组 b 满足以下条件，就称它为山脉：长度至少为 3；存在某个下标 i（0 < i < b.length - 1），使 b[0] 到 b[i] 严格递增，b[i] 到最后一个元素严格递减。

输入整数数组 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 <= 10^4
0 <= arr[i] <= 10^4

进阶：能否只扫描数组一遍？能否只用 O(1) 额外空间？

解题思路：左右两遍预处理上坡下坡长度

枚举山顶。up[i] 表示以 i 结尾、向左连续严格上坡的步数，从左到右递推：arr[i] > arr[i-1] 时 up[i] = up[i-1] + 1，否则为 0。down[i] 同理从右到左递推。两者都大于 0 的位置才能当山顶，山脉长度为 up[i] + down[i] + 1。

为什么正确

up[i] = i 左侧连续严格递增段的长度（不含 i）；down[i] = i 右侧连续严格递减段的长度（不含 i）。

复杂度分析

时间 O(n)，空间 O(n)。

易错点

相等的相邻元素既不算上坡也不算下坡，要用严格大于。另外单调递增或递减的段不是山脉，必须要求 up[i] > 0 且 down[i] > 0。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        up = [0] * n
        down = [0] * n
        for i in range(1, n):
            if arr[i] > arr[i - 1]:
                up[i] = up[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if arr[i] > arr[i + 1]:
                down[i] = down[i + 1] + 1
        ans = 0
        for i in range(n):
            if up[i] > 0 and down[i] > 0:
                ans = max(ans, up[i] + down[i] + 1)
        return ans

class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        int[] up = new int[n];
        int[] down = new int[n];
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                up[i] = up[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                down[i] = down[i + 1] + 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (up[i] > 0 && down[i] > 0) {
                ans = Math.max(ans, up[i] + down[i] + 1);
            }
        }
        return ans;
    }
}

class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size();
        vector<int> up(n, 0);
        vector<int> down(n, 0);
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                up[i] = up[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                down[i] = down[i + 1] + 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (up[i] > 0 && down[i] > 0) {
                ans = max(ans, up[i] + down[i] + 1);
            }
        }
        return ans;
    }
};

func longestMountain(arr []int) int {
	n := len(arr)
	up := make([]int, n)
	down := make([]int, n)
	for i := 1; i < n; i++ {
		if arr[i] > arr[i-1] {
			up[i] = up[i-1] + 1
		}
	}
	for i := n - 2; i >= 0; i-- {
		if arr[i] > arr[i+1] {
			down[i] = down[i+1] + 1
		}
	}
	ans := 0
	for i := 0; i < n; i++ {
		if up[i] > 0 && down[i] > 0 {
			ans = max(ans, up[i]+down[i]+1)
		}
	}
	return ans
}

var longestMountain = function(arr) {
    const n = arr.length;
    const up = new Array(n).fill(0);
    const down = new Array(n).fill(0);
    for (let i = 1; i < n; i++) {
        if (arr[i] > arr[i - 1]) {
            up[i] = up[i - 1] + 1;
        }
    }
    for (let i = n - 2; i >= 0; i--) {
        if (arr[i] > arr[i + 1]) {
            down[i] = down[i + 1] + 1;
        }
    }
    let ans = 0;
    for (let i = 0; i < n; i++) {
        if (up[i] > 0 && down[i] > 0) {
            ans = Math.max(ans, up[i] + down[i] + 1);
        }
    }
    return ans;
};

function longestMountain(arr: number[]): number {
    const n = arr.length;
    const up = new Array(n).fill(0);
    const down = new Array(n).fill(0);
    for (let i = 1; i < n; i++) {
        if (arr[i] > arr[i - 1]) {
            up[i] = up[i - 1] + 1;
        }
    }
    for (let i = n - 2; i >= 0; i--) {
        if (arr[i] > arr[i + 1]) {
            down[i] = down[i + 1] + 1;
        }
    }
    let ans = 0;
    for (let i = 0; i < n; i++) {
        if (up[i] > 0 && down[i] > 0) {
            ans = Math.max(ans, up[i] + down[i] + 1);
        }
    }
    return ans;
}

载入编辑器，自己跑一遍 →

其他解法

预处理法把每个点当山顶、查两侧长度，逻辑清楚；枚举山脚法一次扫描、空间 O(1)，满足题目进阶要求。

解法 2：枚举山脚（双指针一次扫描）时间 O(n)，空间 O(1)

用 left 表示山脉的左山脚。如果 arr[left] < arr[left + 1]，就让 right 一直往上爬到山顶；如果山顶后面是严格下降，再一直往下走到右山脚，用 right - left + 1 更新答案；否则（山顶后是平地或到头）right 再前进一步。处理完把 left 移到 right，右山脚可以直接作为下一座山的左山脚。

只用常数空间，每个元素只被 right 经过一次。但要小心平地和只上不下的情况，指针移动的边界比预处理数组更难写对。

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        ans = 0
        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 + 1 < n 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

class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        int ans = 0, 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 + 1 < n && 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;
    }
}

class Solution {
public:
    int longestMountain(vector<int>& arr) {
        int n = arr.size();
        int ans = 0, 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 + 1 < n && 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;
    }
};

func longestMountain(arr []int) int {
	n := len(arr)
	ans, left := 0, 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+1 < n && arr[right] > arr[right+1] {
				for right+1 < n && arr[right] > arr[right+1] {
					right++
				}
				ans = max(ans, right-left+1)
			} else {
				right++
			}
		}
		left = right
	}
	return ans
}

var longestMountain = function(arr) {
    const n = arr.length;
    let ans = 0, left = 0;
    while (left + 2 < n) {
        let right = left + 1;
        if (arr[left] < arr[left + 1]) {
            while (right + 1 < n && arr[right] < arr[right + 1]) right++;
            if (right + 1 < n && 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;
};

function longestMountain(arr: number[]): number {
    const n = arr.length;
    let ans = 0, left = 0;
    while (left + 2 < n) {
        let right = left + 1;
        if (arr[left] < arr[left + 1]) {
            while (right + 1 < n && arr[right] < arr[right + 1]) right++;
            if (right + 1 < n && 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;
}

动态规划专题的其他题目

查看动态规划全部题目 →