845. Longest Mountain in Array

Problem

Let's call any (contiguous) subarray B (of A) a mountain if the following properties hold:

• B.length >= 3
• There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1] (Note that B could be any subarray of A, including the entire array A.)

Given an array A of integers, return the length of the longest mountain.

Return 0 if there is no mountain.

Example 1:

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

Note:

• 0 <= A.length <= 10000
• 0 <= A[i] <= 10000

Follow up:

• Can you solve it using only one pass?
• Can you solve it in O(1) space?

Main Idea

This problem tests the sliding window technique.

Given an array, the task is to find the length of the longest "mountain" in the array. A "mountain" means starting from a number, gradually increasing, and after reaching the peak, gradually decreasing.

Solution Approach

The solution approach for this problem is also sliding window, except that during the sliding process, you only need to additionally determine the increasing and decreasing states.

Code

package leetcode

func longestMountain(A []int) int {
	left, right, res, isAscending := 0, 0, 0, true
	for left < len(A) {
		if right+1 < len(A) && ((isAscending == true && A[right+1] > A[left] && A[right+1] > A[right]) || (right != left && A[right+1] < A[right])) {
			if A[right+1] < A[right] {
				isAscending = false
			}
			right++
		} else {
			if right != left && isAscending == false {
				res = max(res, right-left+1)
			}
			left++
			if right < left {
				right = left
			}
			if right == left {
				isAscending = true
			}
		}
	}
	return res
}