最长山脉

这个题目可以通过遍历数组来解决，寻找满足条件的最长山脉。我们需要记录每座山脉的起点、峰值和终点，并计算最大长度。

思路如下：

1. 遍历数组：我们从第二个元素开始遍历，直到倒数第二个元素，因为山脉需要左右两侧各有一个递增和递减部分。
2. 寻找峰值：一个元素 nums[i] 是峰值，当它满足 nums[i - 1] < nums[i] > nums[i + 1]。
3. 计算山脉长度：
   • 从峰值开始向左扩展，直到不满足递增条件，记录左边界。
   • 从峰值开始向右扩展，直到不满足递减条件，记录右边界。
   • 计算山脉长度为 right - left + 1，并更新最长山脉长度。
4. 处理特殊情况：如果没有找到任何山脉，返回 0。

代码实现如下：

import java.util.ArrayList;

public class Solution {
    public int longestmountain(ArrayList<Integer> nums) {
        int n = nums.size();
        if (n < 3) return 0;  // 至少需要三个元素形成山脉

        int maxLength = 0;

        for (int i = 1; i < n - 1; i++) {
            // 判断是否为山峰
            if (nums.get(i - 1) < nums.get(i) && nums.get(i) > nums.get(i + 1)) {
                int left = i - 1;
                int right = i + 1;

                // 向左扩展
                while (left > 0 && nums.get(left - 1) < nums.get(left)) {
                    left--;
                }

                // 向右扩展
                while (right < n - 1 && nums.get(right + 1) < nums.get(right)) {
                    right++;
                }

                // 计算当前山脉长度
                int currentLength = right - left + 1;
                maxLength = Math.max(maxLength, currentLength);
            }
        }

        return maxLength;
    }
}

解释

• maxLength 记录最长山脉的长度。
• 每当找到一个满足条件的山峰时，向左右扩展以计算山脉的实际长度。
• 最后返回最大山脉的长度。

复杂度

• 时间复杂度：O(n)，因为我们在遍历数组时只对每个元素做有限次数的比较和扩展。
• 空间复杂度：O(1)，仅使用了固定的额外空间。

package main
//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
*/
func longestmountain( nums []int ) int {
    max:=0
    for i,x:=range nums{
        if i!=0&&i!=len(nums)-1{
            if x>nums[i-1]&&x>nums[i+1]{
                tot:=1
                l,r:=i-1,i+1
                lv,rv:=x,x
                for l>=0&&nums[l]<lv{
                    tot++
                    lv=nums[l]
                    l--
                }
                for r<len(nums)&&nums[r]<rv{
                    tot++
                    rv=nums[r]
                    r++
                }
                if tot>max{
                    max=tot
                }
            }
        }
    }
    return max
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型ArrayList 
     * @return int整型
     */
    public int longestmountain (ArrayList<Integer> nums) {
        int count = 0;
        int res = 0;
        nums.add(10001);
        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i) > nums.get(i - 1)) {
                count++;
            }
            if (nums.get(i) < nums.get(i - 1)) {
                count++;
                if (nums.get(i) <= nums.get(i + 1)) {
                    res = Math.max(res, count + 1);
                    count = 0;
                }
            }
        }
        return res;
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int longestmountain(vector<int>& nums) {
        // write code here
        //两边遍历得到从左到右、从右到左的以各元素为结尾的连续上升子序列长度，分别存在left和right数组中
        vector<int> left(nums.size(),1);
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]>nums[i-1])
            {
                left[i]=left[i-1]+1;
            }
            else
            {
                left[i]=1;
            }
        }
        vector<int> right(nums.size(),1);
        for(int i=nums.size()-2;i>=0;i--)
        {
            if(nums[i]>nums[i+1])
            {
                right[i]=right[i+1]+1;
            }
            else
            {
                right[i]=1;
            }
        }
        int maxx=0;
        for(int i=0;i<nums.size();i++)
        {
            if((left[i]>1)&&(right[i]>1))//两边需要有起伏才符合山脉定义
                maxx=max(maxx,left[i]+right[i]-1);
        }
        return maxx;
    }
};

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/f4e974a50eda429fbf36515a4197b148?tpId=196&tqId=40556&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        left[i]表示以下标i结尾的连续递增子数组的长度，right[i]表示以下标i开头的连续递减子数组的长度。
        初始化：
            left[0] = 1
            right[-1] = 1
        状态转移方程：
            left[i] = left[i - 1] + 1 if nums[i] > nums[i - 1] else 1
            right[i] = right[i + 1] + 1 if nums[i] > nums[i + 1] else 1
        遍历下标1 ~ n - 2，：
            m = left[i] + right[i] - 1
            如果山脉长度m大于等于3，更新res
        找不到山脉，则返回0
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(n)
    """

    def longestmountain(self, nums):
        # write code here
        n = len(nums)

        left, right = [1] * n, [1] * n
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                left[i] = left[i - 1] + 1
        for j in range(n - 2, -1, -1):
            if nums[j] > nums[j + 1]:
                right[j] = right[j + 1] + 1

        res = 0
        for i in range(1, n - 1):
            m = left[i] + right[i] - 1
            if m >= 3:
                res = max(res, m)
        return res


if __name__ == "__main__":
    sol = Solution()

    # nums = [2, 5, 2, 1, 5]

    nums = [2, 2, 2, 2, 1]

    res = sol.longestmountain(nums)

    print res