Leetcode日记–Longest mountains in array

发布于 2020-10-25  106 次阅读


碎碎念:昨天国家德比跟吃了屎似的,拉莫斯是真的恶心,经典演员行为。

题目如下:

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.

思路

总之题目就是在找某点,左边为严格递增数列,右边为严格递减数列,然后返回某个左右数列长度和最长的值。

思路一(双指针,枚举山脚,空间复杂度更低):

对于这种有左右边界的问题很容易想到使用双指针来解决问题。

我们设定左右指针(其实左指针是固定的,用来表明左边界)。

算法如下:

首先,因为山的长度至少为3,因此我们需要left+2<n。不满足则说明这个左边界后面不可能形成山了。

然后我们把右指针设为left+1,并在A[right]<A[right+1]的时候持续移动右指针。

当不满足的时候,我们需要判断是否有A[right]>A[right+1](若相等则也不为山顶),若A[right]>A[right+1]成立,则说明已经找到山顶。

我们再使用A[right]>A[right+1]这个条件移动右指针,直到直到山脚。

这时的右山脚同时应该也是下一轮的左山脚。因此我们令left=right。

并求当前res为res和(left-right+1)中的最大值。

代码如下:

class Solution {
    public int longestMountain(int[] A) {
        int n = A.length;
        int ans = 0;
        int left = 0;
        while (left + 2 < n) {
            int right = left + 1;
            if (A[left] < A[left + 1]) {
                while (right + 1 < n && A[right] < A[right + 1]) {
                    ++right;
                }
                if (right < n - 1 && A[right] > A[right + 1]) {
                    while (right + 1 < n && A[right] > A[right + 1]) {
                        ++right;
                    }
                    ans = Math.max(ans, right - left + 1);
                } else {
                    ++right;
                }
            }
            left = right;
        }
        return ans;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/longest-mountain-in-array/solution/shu-zu-zhong-de-zui-chang-shan-mai-by-leetcode-sol/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法二(动态规划,枚举山顶,我当时没想到,空间复杂度为O(n)):

动态规划的思路是分别从左往右(可以利用之前的结果)得到左山坡的长度,再从右往左得到右山坡的长度。

我们利用left数组来记录左山坡的长度。

若A[i-1]<A[i]则有

left[i]=left[i-1]+1

否则说明左边界无法拓展了。那么将left[i]置为零。

右边界类似的思路从右往左遍历得到结果。

最终遍历每个点,取res为当前res和 right[i]+left[i]+1 中的最大值。

代码如下:

class Solution {
    public int longestMountain(int[] A) {
        int n = A.length;
        if(n<=2)
            return 0;
        int res=0;
        int[] left = new int[n];
        for(int i=1;i<n;i++){
            left[i] = A[i-1]<A[i]?left[i-1]+1:0; 
        }
        int[] right = new int[n];
        for(int i=n-2;i>0;i--){
            right[i] = A[i+1]<A[i]?right[i+1]+1:0;
        }
        for(int i=0;i<n;i++){
            if(right[i]>0&&left[i]>0)
                res = Math.max(res,left[i]+right[i]+1);
        }
        return res;
    }
}

你好哇!欢迎来到雷公马碎碎念的地方:)