Java O(n) soution (Convex Hull Window)


  • 0
    S

    The original post and python solution by @awice is here

    I just convert it to the java version

    public class Solution {
        //convex hull window
        public double findMaxAverage(int[] nums, int k) {
           int n = nums.length;
           long[] sum = new long[n+1];
            
           for(int i = 0; i < n; i++){
               sum[i+1] = sum[i] + nums[i];
           }
            
           LinkedList<Integer> hull = new LinkedList<>();
           double ans = Integer.MIN_VALUE;
            
           for(int j = k - 1; j < n; j++){
                while(hull.size() >= 2 && getAvg(sum, hull.get(hull.size() - 2), hull.get(hull.size() - 1) - 1) >= getAvg(sum, hull.get(hull.size() - 2), j-k)){
                   hull.remove(hull.size() - 1);
                }
                     
                hull.add(j - k + 1);
                while(hull.size() >= 2 && getAvg(sum, hull.get(0), hull.get(1) - 1) <= getAvg(sum, hull.get(0), j)){
                    hull.removeFirst();
                }
                      
                ans = Math.max(ans, getAvg(sum, hull.getFirst(), j));
           } 
            
            return ans;
        }
        
        
        private double getAvg(long[] sum, int i, int j){
            return (sum[j+1] - sum[i])/(double) (j+1-i);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.