LeetCode 845 -- the longest mountain range in the array

1. topic

2. answers

2.1 method 1

The left array represents the number of elements smaller than the current element on the left side of the current element, and the right array represents the number of elements smaller than the current element on the right side of the current element. In the middle of the mountain, B[i], there must be elements smaller than B[i] on the left and right, and the length of the mountain is left[i] + right[i] + 1.

class Solution {
public:
    int longestMountain(vector<int>& A) {
        
        int n = A.size();
        if (n < 3)    return 0;
        
        vector<int> left(n, 0);
        vector<int> right(n, 0);
        
        for (int i = 1; i < n; i++)
        {
            if (A[i] > A[i-1])  left[i] = left[i-1] + 1;
        }
        
        for (int i = n-2; i >= 0; i--)
        {
            if (A[i] > A[i+1])  right[i] = right[i+1] + 1;;
        }
        
        int len = 0;
        for (int i = 0; i < n; i++)
        {
            if (left[i] != 0 && right[i] != 0)
                len = max(len, left[i] + right[i] + 1);
        }
        
        return len;   
    }
};

2.2 method 2

If the array is 1, the current element is larger than the left element. If the array is 1, the current element is larger than the right element.

In the case of mountains, the two arrays should be in the following sequence

Array value
max_than_left 1 (optional) ... 1 (selected) ... 0 (optional)
max_than_right 0 (optional) ... 1 (selected) ... 1 (optional)
class Solution {
public:
    int longestMountain(vector<int>& A) {
        
        
        int n = A.size();
        if (n < 3)    return 0;
        
        vector<int> max_than_left(n, 0);
        vector<int> max_than_right(n, 0);
        
        for (int i = 1; i < n; i++)
        {
            if (A[i] > A[i-1])  max_than_left[i] = 1;
        }
        
        for (int i = 0; i < n-1; i++)
        {
            if (A[i] > A[i+1])  max_than_right[i] = 1;
        }
        
        int result = 0;
        int len = 0;
        int left_flag = 0;
        int middle_flag = 0;
        int right_flag = 0;
        
        for (int i = 0; i < n; i++)
        {
            if (max_than_left[i] == 1 && max_than_right[i] == 0)
            {
                if (left_flag)  result++;    
                else    
                {
                    result = 3;
                    left_flag = 1;
                }   
            }
            else if (max_than_left[i] == 1 && max_than_right[i] == 1)
            {
                if (left_flag)  
                {
                    result++;  
                }
                else
                {
                    result = 3;
                }
                
                left_flag = 0;
                middle_flag = 1;
            }
            else if (max_than_left[i] == 0 && max_than_right[i] == 1)
            {
                if (right_flag) result++;
                if (middle_flag)     
                {
                    middle_flag = 0;
                    right_flag = 1;
                    result++;
                }  
            }
            else
            {
                right_flag = 0;
                middle_flag = 0;
                left_flag = 0;
                result = 0;
            }
            if (middle_flag || right_flag) len = max(len, result);
        }
        
        return len;
        
    }
};

For more highlights, please pay attention to "seniusen"!

Posted on Sun, 01 Dec 2019 07:07:34 -0800 by pucker22