845. Longest Mountain in Array

Problem Statement

link: LeetCode.cn LeetCode

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:

Input: arr = [2,1,4,7,3,2,5] Output: 5

Input: arr = [2,2,2] Output: 0

Solution Approach

The algorithm iterates through the array, identifying peaks (increasing followed by decreasing elements). It calculates the length of each mountain subarray and returns the maximum length found.

Algorithm

1. Initialize Variables: Initialize variables res (result) and left as 0. These variables will track the length of the longest mountain subarray and the left index of the potential mountain respectively.
2. Iterate through the Array: Use a while loop to iterate through the array arr while left + 2 < n, where n is the length of arr. This loop identifies potential mountain subarrays.
3. Identify Mountain Subarrays: Within the loop, for each left index, find the peak of the mountain subarray. Once a peak is found, extend the right end of the mountain subarray as far as possible while the mountain condition holds true (continuously decreasing elements). Calculate the length of the mountain subarray and update res if it’s longer than the previously found mountains. Move the left pointer to the right end of the mountain subarray to continue searching for more mountains.

Implement

    class Solution:
      def longestMountain(self, arr: List[int]) -> int:
          n = len(arr)
          res = 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
                      res = max(res, right - left + 1)
                  else:
                      right += 1
              left = right
          return res

       

    
    

Twitter  facebook  Email