原题地址（中等）

方法1—动态规划

思路

以i作为山顶，向左右延续
这个是我没想到的，是官方的解法，定义两数组left,right
left[i]表示从i向左可以延续的个数
left[i] = left[i-1] + 1, if A[i] > A[i-1]
= 0, else

right[i]表示从i向右可以延续的个数
right[i] = right[i+1] + 1, if A[i] > A[i+1]
= 0, else

代码

  1. class Solution {
  2. public:
  3.     int longestMountain(vector<int>& A) {
  4.         int len = A.size();
  5.         if(len < 3)     return 0;
  6.         vector<int> left(len, 0), right(len, 0);
  7.         for(int i=1; i<len; i++){
  8.             if(A[i] > A[i-1])   left[i] = left[i-1] + 1;
  9.         }
  10.         for(int i=len-2; i>=0; i--){
  11.             if(A[i] > A[i+1])   right[i] = right[i+1] + 1;
  12.         }
  13.         int ans = 0;
  14.         for(int i=1; i<len; i++) {
  15.             if(left[i] && right[i])
  16.                 ans = max(ans, left[i]+right[i]+1);
  17.         }
  18.         return ans;
  19.     }
  20. };

时空复杂度

都是O(N)

方法2—贪心

思路

这个是我自己的思路
思路很简单，就是找从左到右找符合题意的山，找到后，记录山的长度，然后再找，再记录。
有一些细节很坑，提交了两次之后才改对的。

总体来说就是：
找到符合题意的山，记录长度，然后指针直接移动到山的右侧，继续找下一座；
没找到符合题意的山，指针就移动到下一个；

代码

  1. class Solution {
  2. public:
  3.     int longestMountain(vector<int>& A) {
  4.         int i = 1, len = A.size(), ans = 0;
  5.         if(len < 3)     return 0;
  6.         while(i < len) {
  7.             int begin = i-1;
  8.             while(i < len && A[i-1] < A[i]){
  9.                 i++;
  10.             }
  11.             while(i < len && A[i-1] > A[i]){
  12.                 i++;
  13.             }
  14.             int end = i-1;
  15.             if(A[(begin+end)/2] > A[begin] && A[(begin+end)/2] > A[end])  ans = max(ans, end-begin+1);
  16.             if(begin == end)    i++;
  17.         }
  18.         if(ans < 3)     return 0;
  19.         else    return ans;
  20.     }
  21. };

时空复杂度

时间O(N) 空间O(1)