Leetcode P2256 最小平均值 Java使用动态规划去解决此问题

Leetcode P2256 最小平均值 Java使用动态规划去解决此问题

执行用时：8 ms, 在所有 Java 提交中击败了23.75%的用户

内存消耗：57.6 MB, 在所有 Java 提交中击败了92.99%的用户

ideas

首先我们要做一些特殊情况的判断，例如当前数组没有元素

      if (nums.length == 0){
            return -1;
        }

接下来我们创建2个DP数组，一个负责数组中的元素从左到右的累加和，一个是从右到左的累加和。

        long[] ldp = new long[nums.length];
        long[] rdp = new long[nums.length];

        ldp[0] = nums[0];

        for (int i = 1; i < ldp.length; i++) {
            ldp[i] = ldp[i-1] + nums[i];

        }

        rdp[rdp.length-1] = nums[rdp.length-1];
        for (int i = rdp.length-2; i >= 0 ; i--) {
            rdp[i] = nums[i] + rdp[i+1];
        }

接下来就遍历数组进行计算两个数的 绝对差 是两者差的绝对值

在判断的过程中我们要注意下，如果当前下标到了数组最后一位的情况那么我们就把当前下标右侧的值设置为0

同时我们要注意，我们进行累加和可能会超出int类型的范围，所以我们累加要用long类型

            long frontsumofarray = ldp[i];
            long bhindsumofarray = 0;
            //查看i是否到达数组的最后一位
            if (i+1 >= nums.length){
                bhindsumofarray = 0;
            }else{
                bhindsumofarray = rdp[i+1];
            }

记录最小两个数的 绝对差 是两者差的绝对值的下标就是将每次最小绝对值的下标记录下来

            //记录最小两个数的 绝对差 是两者差的绝对值的下标
            if (lastminnumber > temp){
                lastminnumber = temp;
                res = i;
            }

code

class Solution {
    public int minimumAverageDifference(int[] nums) {
       if (nums.length == 0){
            return -1;
        }
        int res = 0;
        int lastminnumber =Integer.MAX_VALUE;
        long[] ldp = new long[nums.length];
        long[] rdp = new long[nums.length];

        ldp[0] = nums[0];

        for (int i = 1; i < ldp.length; i++) {
            ldp[i] = ldp[i-1] + nums[i];

        }

        rdp[rdp.length-1] = nums[rdp.length-1];
        for (int i = rdp.length-2; i >= 0 ; i--) {
            rdp[i] = nums[i] + rdp[i+1];
        }

        //计算绝对值
        for (int i = 0; i < nums.length; i++) {
            long frontsumofarray = ldp[i];
            long bhindsumofarray = 0;
            //查看i是否到达数组的最后一位
            if (i+1 >= nums.length){
                bhindsumofarray = 0;
            }else{
                bhindsumofarray = rdp[i+1];
            }

            int frontcountofarr = i+1;
            int bhindcountofarr = nums.length -i-1;

            //计算平均差
            int front = (int) (frontsumofarray/frontcountofarr);
            int bhind = i+1 >= nums.length ? 0 : (int) (bhindsumofarray/bhindcountofarr);
            int temp  = Math.abs(front-bhind);

            //记录最小两个数的 绝对差 是两者差的绝对值的下标
            if (lastminnumber > temp){
                lastminnumber = temp;
                res = i;
            }
        }

        return res;
    }
}