LongestMountainInArray [source code]

public class LongestMountainInArray {
static
/****************************************************************************/
class Solution {
    public int longestMountain(int[] A) {
        if (A.length < 3)
            return 0;
        int max_len = 0, N = A.length, anchor = N;
        for (int i = 0; i < N; i++) {
            if (i > 0 && A[i] < A[i - 1]) {
                max_len = Math.max (max_len, i - anchor + 1);
            }
            if (anchor < N && i > 0 && A[i] == A[i - 1]) {
                anchor = N;
            } else if (i < N - 1 && A[i] < A[i + 1] && (i == 0 || A[i] <= A[i - 1])) {
                anchor = i;
            }
        }
        return max_len;
    }
}
/****************************************************************************/

    public static void main(String[] args) {
        LongestMountainInArray.Solution tester = new LongestMountainInArray.Solution();
        int[][] inputs = {
            {2,1,4,7,3,2,5}, {5},
            {2,2,2}, {0},
            {0,1,2,3,4,5,4,3,2,1,0}, {11},
            {1,1,0,0,1,0}, {3},
            {2,3,3,2,0,2}, {0},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            System.out.println (Printer.separator ());
            int[] A = inputs[2 * i];
            int ans = inputs[2 * i + 1][0], output = tester.longestMountain (A);
            System.out.printf ("%s\n%s\n%d\n", 
                Printer.array (A), Printer.wrap (output + "", output == ans ? 92 : 91), ans
            );
        }
    }
}

哎呀这题, 看起来好像有点难啊, 好像是一个DP题目;

DP题目, 真的真的, 求你了, 别秀了, 不要以为自己脑子里完全抽象的理解就能解出来, 动动手走几个具体的例子求求你了, 头皮发麻;

对于mountain的定义还是比较清晰的; example2给的这个, 我感觉可以一开始主逻辑里面直接忽略, 然后最后找到的mountain(至少能找到一个长度为1的感觉), 最后检查一下是不是足够长度就行了?

当然也可以直接实现的时候就要求长度至少是3, 小问题, 先不纠结了;

走了一下具体的例子, 感觉一个简单的DP应该可以, 随便写写看;

突然发现好像根本不用DP? 直接找到所有的maximal uptick就行了, 一个greedy的做法应该能够搞定;
想想怎么维护信息;

从左到右, uptick上面的点, 应该记忆左边最近的山谷, 然后downtick上面的点, 应该记忆左边最近的山顶; 记忆的都是index; 这样我们当最后走downtick的时候, 每一个点, 找到自己左边最近山顶, 然后自己对应的mountain长度就是index-山顶.left_山谷.
好像可以更简单, 只关注所有的山谷就行了?

看起来有点傻的算法, 写写看;

被test3给break了, 为了解决这个test, 感觉用imply做法好像简单一些;
不过对于这个题目, 直接自己写其实也很简单, 逻辑比较简单;

test4才看出来这个问题的难点了, 如果山谷是平原, 也要考虑的;
怎么修改, 直接两个<那里都加上一个等号呢? 不行的, 因为只有一头可以去等号; 这个怎么表达? 当时425应该是有教了的, 忘记了;
要表达的应该是, 至多有一个等号;

else if (A[i] < A[i + 1] && !equal_used) {  
            right_good = true;  
        }

又中了一次&&header陷阱.

写到这里没有发现一个重要的问题, 比如:1 0 0 1这样的一个, 你发现一个问题没有, 我之前有一个assumption是不对的: 山谷是可以分开的, 这里实际上有一个下降山谷, 和一个上升山谷: 他们不在同一个点上;

这个时候我的代码是:

class Solution {  
    public int longestMountain(int[] A) {  
        if (A.length < 3)  
            return 0;  
        int max_len = 0, N = A.length, prev = -1;  
        for (int i = 0; i < N; i++) {  
            if (good (i, A)) {  
                if (prev < 0) {  
                    prev = i;  
                } else {  
                    max_len = Math.max (max_len, i - prev + 1);  
                }  
            }  
        }  
        return max_len;  
    }  

    boolean good (int i, int[] A) {  
        int N = A.length;  
        boolean left_good = false, right_good = false, equal_used = false;  
        if (i == 0) {  
            left_good = true;  
            equal_used = true;  
        } else if (A[i] <= A[i - 1]) {  
            left_good = true;  
            if (A[i] == A[i - 1])  
                equal_used = true;  
        }  
        if (i == N - 1) {  
            right_good = true;  
            equal_used = true;  
        } else if (A[i] <= A[i + 1]) {  
            right_good = !equal_used || A[i] != A[i + 1];  
        }  
        return left_good && right_good;  
    }  
}

这个就不对了, 因为这个代码的一个隐藏的要求就是山谷必须是唯一的点;

怎么修改? 好难啊; well, 一个mountain的长度是一个下降山谷的位置减去一个上升山谷的位置; 所以好像也是可以解决的;

好像就是一个分段函数就行了;

前面得到的一个教训就是, 如果比如你要判断一个上升沿, 那么这个上升沿的左边是可以取等号的, 右边是不可以的; 这个应该可以用到;

用trigger写法好像有点麻烦, 用run写法来写写看? 对上升沿有一个复杂判断, 至于下降沿, 不管;

这个时候的主循环:

            if (i > 0 && A[i] < A[i - 1]) {  
                max_len = Math.max (max_len, i - anchor + 1);  
            }  
            if (i < N - 1 && A[i] < A[i + 1] && (i == 0 || A[i] <= A[i - 1])) {  
                anchor = i;  
            }

注意两个地方:

• 不能用else连接, 因为上升沿实际上也可能同时是一个downtick当中的一份子, 所以也要用来更新max_len;
• 两个if的顺序很重要, 更新max_len一定要在更新anchor之前;

但是这个代码还是被test5给break了; 然后我发现这题好像还是得用DP来写? 不对, 这里当我走到233的时候, 我是不是可以直接把当前这个run给断了?

最后好不容易是AC了, 写的一手好bug;

这题实际上还是挺有意思的, 虽然最后的算法还是挺简单的, 但是我中间还是有大量的思考过程, 很有意思(对, 写bug也很有意思, 不过我之前那个代码的那种bug, 基本就是严重的会导致挂面试的bug了);

UNFINISHED

uwi:5.5min

class Solution {  
    public int longestMountain(int[] a) {  
        int n = a.length;  
        int max = 0;  
        for(int i = 0;i < n;i++){  
            int j = i-1, k = i+1;  
            for(;j >= 0 && a[j] < a[j+1];j--);  
            for(;k < n && a[k-1] > a[k];k++);  
            if(i-j > 1 && k-i > 1){  
                int len = k-j-1;  
                max = Math.max(max, len);  
            }  
        }  
        return max;  
    }  
}

Problem 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 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

Difficulty:Medium
Total Accepted:1.2K
Total Submissions:4.4K
Contributor: