[LeetCode] 845. Longest Mountain in Array

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?

数组中的最长山脉。题意是给一个数组，请你返回一个最长的山脉数组。山脉数组的定义是

B.length >= 3
存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

这道题不涉及算法，思路是双指针。我先给一个需要额外空间的做法。创建两个额外数组，与input数组等长，一个叫做up，一个叫做down，目的是记录数组中间单调递增和单调递减的部分到底有多长。首先把数组从右往左扫描，判断nums[i] > nums[i + 1]。如果满足这个条件，就down[i] = down[i + 1] + 1，记录一个局部的递减子数组的长度。一旦不满足这个条件的话，down[i] = 0。

再次扫描数组，这一次从左往右扫描，如果nums[i] > nums[i - 1]，则up[i] = up[i - 1] + 1，这是在记录一个局部的递增子数组的长度。同时我们可以计算最大子数组的长度了，如果up[i] > 0 && down[i] > 0, res = up[i] + down[i] + 1。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int longestMountain(int[] A) {
 3         int len = A.length;
 4         int res = 0;
 5         int[] up = new int[len];
 6         int[] down = new int[len];
 7         for (int i = len - 2; i >= 0; i--) {
 8             if (A[i] > A[i + 1]) {
 9                 down[i] = down[i + 1] + 1;
10             }
11         }
12 
13         for (int i = 0; i < len; i++) {
14             if (i > 0 && A[i] > A[i - 1]) {
15                 up[i] = up[i - 1] + 1;
16             }
17             if (up[i] > 0 && down[i] > 0) {
18                 res = Math.max(res, up[i] + down[i] + 1);
19             }
20         }
21         return res;
22     }
23 }

另外我这里再提供一种不需要额外空间的做法，只扫描一次。从左往右扫描数组，如果nums[i] > nums[i - 1]，那么这一段就是上升的，用一个变量记录最大的上升长度up；这里我们是用一个while循环控制，所以一旦跳出这个while循环你就知道可能要开始下降了（也有可能是平的，这里要注意）。所以这时我们再用一个变量down记录下降部分的长度，也用while循环控制，当不满足while的条件的时候，down也停止记录了。此时如果up和down都大于0，就更新res。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int longestMountain(int[] A) {
 3         int max = 0;
 4         int i = 1;
 5         while (i < A.length) {
 6             while (i < A.length && A[i - 1] == A[i]) {
 7                 i++;
 8             }
 9             int up = 0;
10             while (i < A.length && A[i - 1] < A[i]) {
11                 up++;
12                 i++;
13             }
14 
15             int down = 0;
16             while (i < A.length && A[i - 1] > A[i]) {
17                 down++;
18                 i++;
19             }
20             if (up > 0 && down > 0) {
21                 max = Math.max(max, up + down + 1);
22             }
23         }
24         return max;
25     }
26 }

LeetCode 题目总结