Java One Pass O(N), decrease 1 method


  • 0
    A

    Easy to know that we can just pick one to decrease, which means we need to decrease all other to the minimum.

    Don' t have to use one loop first to find the min.
    When we find the a lower number, just update the moves and min, since all the number on the left of the current min must be larger than current min.

    We can also sum them up and minus ( len * min ) at last. Just like a bar graph.

    public int minMoves(int[] nums) {
            if(nums==null)
                return 0;
            int min=nums[0];
            int moves=0;
            for(int i=1; i<nums.length; i++){
                if(nums[i]>=min){
                    moves+=nums[i]-min;
                }
                else{
                    moves+= i * (min-nums[i]); 
                    min=nums[i];
                }
            }
            return moves;
        }
    

Log in to reply
 

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