linux.do

Leetcode每日一题 —— 1526. 形成目标数组的子数组最少增加次数(困难)

1526. 形成目标数组的子数组最少增加次数

思路
第一反应，贪心+分治就行，这真的是困难题吗？每次贪心区间最小值，然后分段递归结果。

代码

    private int[] target;
    public int minNumberOperations(int[] target) {
        this.target = target;
        return calc(0, 0, target.length - 1);
    }

    public int calc(int low, int left, int right) {
        if (left == right) {
            return target[left] - low;
        }
        ArrayList<int[]> span = new ArrayList<>();
        int min = target[left];
        int last = left;
        for (int i = left + 1; i <= right; i++) {
            if (target[i] < min) {
                min = target[i];
                span.clear();
                span.add(new int[]{left, i - 1});
                last = i;
            } else if (target[i] == min) {
                if (i > last + 1) {
                    span.add(new int[]{last + 1, i - 1});
                }
                last = i;
            }
        }
        if (last <= right - 1) {
            span.add(new int[]{last + 1, right});
        }
        int ans = min - low;
        for (int[] ints : span) {
            ans += calc(min, ints[0], ints[1]);
        }
        return ans;
    }

时间复杂度：O(n^2)
空间复杂度：O(n)

优化思路
但是！但是！写完后发现时间复杂度最差情况下会退化到O(n^2)，看范围1 <= target.length <= 10^5大概率会超时。
我需要优化分段方法，或者换个思路。那么我能不能一次分段呢？
如果把数组看出一个线段，那么波峰波谷之间的差值就是需要操作的次数，中间部分无需关注，这样就能一次分段了。只需要找到所有的波谷分段，分段过程中记录波峰，然后每次进行削峰操作。

代码

    public int minNumberOperations(int[] target) {
        if (target.length == 1) return target[0];
        ArrayList<Integer> list = new ArrayList<>();
        int last = 0;
        list.add(0);
        for (int num : target) {
            if (num != last) {
                list.add(num);
                last = num;
            }
        }
        if (last != 0) list.add(0);
        int top = 0;
        int ans = 0;
        int[] lastBottom = null;
        for (int i = 1; i < list.size() - 1; i++) {
            int v = list.get(i);
            if (v < list.get(i - 1) && v < list.get(i + 1)) {
                if (lastBottom == null) {
                    lastBottom = new int[]{v, top};
                } else {
                    if (v >= lastBottom[0]) {
                        ans += top - lastBottom[0];
                        lastBottom[0] = v;
                    } else {
                        ans += top - v;
                    }
                }
                top = 0;
            } else if (v > top) {
                top = v;
            }
        }
        ans += top;
        if (lastBottom != null) {
            ans += lastBottom[1] - lastBottom[0];
        }
        return ans;
    }

时间复杂度：O(n)
空间复杂度：O(n)

优化思路
PS.一开始想求出分段后依次削峰的，后来发现可以边分边削。
过了，但是！居然是较慢的那一批，已经是O(n)了呀。。。可能使用List影响了效率，另外在考虑削峰的过程中，发现似乎可以根据前缀直接得到是否需要削峰、要削多少，等下午下班再考虑优化下(如果我记得并且懒癌没有发作的话)。

1 post - 1 participant

Read full topic

via LINUX DO - 最新话题 (author: 魔法师)

37 views04:33