Problem
题目大意:找出最长的山形子数组。
https://leetcode.com/problems/longest-mountain-in-array/description/
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 thatB[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
Solution: DP
Three passes
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua // Running time: 24 ms class Solution { public: int longestMountain(vector<int>& A) { vector<int> inc(A.size()); vector<int> dec(A.size()); for (int i = 1; i < A.size(); ++i) if (A[i] > A[i - 1]) inc[i] = inc[i - 1] + 1; for (int i = A.size() - 2; i > 0; --i) if (A[i] > A[i + 1]) dec[i] = dec[i + 1] + 1; int ans = 0; for (int i = 0; i < A.size(); ++i) if (inc[i] && dec[i]) ans = max(ans, inc[i] + dec[i] + 1); return ans >= 3 ? ans : 0; } }; |
One pass
Time complexity: O(n)
Space complexity: O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Running time: 24 ms class Solution { public: int longestMountain(vector<int>& A) { int inc = 0; int dec = 0; int ans = 0; for (int i = 1; i < A.size(); ++i) { if (dec && A[i] > A[i - 1] || A[i] == A[i - 1]) dec = inc = 0; inc += A[i] > A[i - 1]; dec += A[i] < A[i - 1]; if (inc && dec) ans = max(ans, inc + dec + 1); } return ans >= 3 ? ans : 0; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment