三道coding challenge from hired.com (Hill,Deviation ,Maximum Difference)

大家好，小弟献丑了，我帖2个题目我写的，感觉代码比上面大家讨论的都要简洁一些：
Hill 和 Maximum Difference， 这两个题目都可以用类似dp方法解，都是O(N)复杂度的。
先贴个Hill的：

class MyClass {
    public static void hill(Integer[] v) {
        int maxDiff = 0;
        int max= v[0]-0;
        for (int i=1; i<v.length; i++) {
            max = Math.max(max,v[i]-i);
            maxDiff = Math.max(maxDiff, max-(v[i]-i));
        }
        System.out.println((maxDiff+1)/2);
    }
}

然后是Maximum Difference， 这题实际思路和Leetcode的Best Time to Buy and Sell Stock III 非常类似，大家好好做下那个题吧。
这题的O(N)可以是3N (上面有同学帖的我没仔细看，应该就是扫描3遍的)，我贴一个扫描2遍的，虽然也是O(N) 就是稍微好那么一点吧，其实就是在第2遍从右往左扫的时候顺便把最终结果也给算出来了。

class MyClass {
    public static void maxdiff(Integer[] v) {
        int min_endinghere=0;
        int min_sofarr = 0;
        int[] min_sofar = new int[v.length];
        for (int i=0;i<v.length;i++){
            min_endinghere += v[i];
            if (min_endinghere>0) min_endinghere=0;
            min_sofarr = Math.min(min_sofarr,min_endinghere);
            min_sofar[i] = min_sofarr;
        }
        int max_endinghere=0;
        int max_sofar = 0;
        int max_diff=0;
        for (int i=v.length-1;i>=0;i--){
            max_endinghere += v[i];
            if (max_endinghere<0) max_endinghere=0;
            max_sofar = Math.max(max_sofar,max_endinghere);
            max_diff = Math.max(max_diff,max_sofar-min_sofar[i]);
        }
        System.out.println(max_diff);
    }
}

没有仔细说Hill的思路，我再来说下，
楼上有同学说了，实际上是v[i]-i构成的这个新的数组，找到最大的（左-右）差值，左是相对靠左的某数，左和右可以不相邻。
然后在第i步，更新到此为止的出现的最大的数（左），然后用（左-当前）去更新最大的(左-右)差值 - 即maxDiff这个变量。

co89757 发表于 2014-1-15 05:25
3. Maximum DIfference
if I understand it correctly, the aim is look for max_diff = sum(right_subse ...

恩，这个可以存从左边过来的最大sum，最少sum和右边过来的最小sum和最大sum。这样就能在O(N)的时间里面解决了。

denilsen 发表于 2015-1-14 04:45
大家好，小弟献丑了，我帖2个题目我写的，感觉代码比上面大家讨论的都要简洁一些：
Hill 和 Maximum Diffe ...

从时间复杂度上两者是没有差别的。你一个循环体里面做10件事和10个循环体各做一件事，最后的时间复杂度是一样的，但是你的方法可以节省空间。

刚刚去试hired online test没有做出来果然应该常来地里逛一逛！

第二题find deviation 我是这么做的，带入sample运行结果满足要求。只是time complexity是O(n^2), 不知道是否满足题目要求的 ”print the result in less than 2 seconds“ 。谁有更优化的解法，可以分享下。

1. public class Deviation {
   
2.         public static void main(String[] args){
   
3.                 int[] v = {6, 9, 4, 7, 4, 1};
   
4.                 int d = 3;
   
5.                 int res = 0;
   
6.                 for(int i=0;i < v.length - d + 1; i++){
   
7.                         int max = v[i], min = v[i];
   
8.                        
   
9.                         for(int j=i; j<i + d; j++){
   
10.                                 if(v[j] > max){
    
11.                                         max = v[j];
    
12.                                 }else if(v[j] < min){
    
13.                                         min = v[j];
    
14.                                 }
    
15.                         }
    
16.                         res = Math.max(res, (max - min));
    
17.                 }
    
18.                 System.out.println(res);
    
19.         }
    
20. }

复制代码

denilsen 发表于 2015-1-14 04:45
大家好，小弟献丑了，我帖2个题目我写的，感觉代码比上面大家讨论的都要简洁一些：
Hill 和 Maximum Diffe ...

我的错，你的算法给力。 细节处理也很到位 谢谢分享

小弟第二题是这么做的，简单的思路。 复杂度是O(nlg(d));

1. public static int deviation(int[] A, int d){
   
2.                 if(A.length < d) throw new IllegalArgumentException();
   
3.                 Queue<Integer> queueMin = new PriorityQueue<>();
   
4.                 PriorityQueue<Integer> queueMax = new PriorityQueue<Integer>(d, new Comparator<Integer>(){
   
5.                         public int compare(Integer n1, Integer n2){
   
6.                                 return n2 - n1;
   
7.                         }
   
8.                 });
   
9.                 int min = Integer.MAX_VALUE;
   
10.                 int max = Integer.MIN_VALUE;
    
11.                 int res = Integer.MIN_VALUE;
    
12.                 for(int i = 0; i < A.length; i++) {
    
13.                         if(queueMax.size() < d) {
    
14.                                 queueMax.add(A[i]);
    
15.                                 queueMin.add(A[i]);
    
16.                         } else {
    
17.                                 queueMax.remove(A[i - d]);
    
18.                                 queueMin.remove(A[i - d]);
    
19.                                 queueMax.add(A[i]);
    
20.                                 queueMin.add(A[i]);
    
21.                         }
    
22.                         if(queueMax.size() >= d){
    
23.                                 min = queueMin.peek();
    
24.                                 max = queueMax.peek();
    
25.                                 System.out.println("max = " + max + "min = " + min );
    
26.                                 res = Math.max(max - min, res);
    
27.                         }
    
28.                 }
    
29.                 return res;
    
30.         }

复制代码

NdrZmansN 发表于 2014-12-5 06:07
我也做了hired的challenge.当时也卡在hill这个题上了.事后想出的解法:思路是: 先把每个数减去它的index. 这 ...

我觉得这个太棒了，一下子就懂了，谢谢你哦