LEETCODE 1526. Minimum Number of Increments on Subarrays to Form a Target Array 解题思路分析

题目大意:

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

给你一个整数数组 target 和一个数组 initial ,initial 数组与 target  数组有同样的维度,且一开始全部为 0 。

请你返回从 initial 得到  target 的最少操作次数,每次操作需遵循以下规则:

  • 在 initial 中选择 任意 子数组,并将子数组中每个元素增加 1 。

答案保证在 32 位有符号整数以内。

示例 1:

输入:target = [1,2,3,2,1]
输出:3
解释:我们需要至少 3 次操作从 intial 数组得到 target 数组。
[0,0,0,0,0] 将下标为 0 到 4 的元素(包含二者)加 1 。
[1,1,1,1,1] 将下标为 1 到 3 的元素(包含二者)加 1 。
[1,2,2,2,1] 将下表为 2 的元素增加 1 。
[1,2,3,2,1] 得到了目标数组。

示例 2:

输入:target = [3,1,1,2]
输出:4
解释:(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2](target)。

示例 3:

输入:target = [3,1,5,4,2]
输出:7
解释:(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1]
-> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target)。

示例 4:

输入:target = [1,1,1,1]
输出:1

提示:

  • 1 <= target.length <= 10^5
  • 1 <= target[i] <= 10^5

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1526

解题思路分析:

这道题并不难,先说结论,本题的关键在于查看每个位置与相邻左边的高度差,如果高于左边,那么将其差值累加至返回结果即可。举个例子:[3,1,5,4,2]

  1. 首位3的左边没有数字,那么它与左边的高度差为3,累加至返回结果。返回结果为3。
  2. 第二位1小于左边的3,跳过。
  3. 第三位5与左边1的高度差为4,累加至返回结果。返回结果为7。
  4. 第四位4小于左边的5,跳过。
  5. 第五位2小于左边的4,跳过。
  6. 返回结果为7。

接下来证明一下该思路。数组中每一位上的数字都可以看做是一个高度,对于任意一点,它与左边的高度差只有三种可能:大于小于或者等于。

  1. 当高度相同时,显然,两个位置共享同样的操作即可达到当前效果,也就是说当前位置无须额外操作。
  2. 如果当前高度小于左侧高度的话,那么当前位置同样可以共享前一位置的操作。比如[2,1],当前位置高度为1,由于左侧高度为2,我们可以将其看作为2层建筑。下层为区间0到1,这正好包含了当前下标1的位置。上层区间为0到0。因此当前位置同样无须额外操作。
  3. 如果当前高度大于左侧高度,那么当前位置必须进行操作才能满足新增的高度差,而操作次数应等于该高度差。
  4. 注意数组首位与左侧的高度差为首位的高度。

实现代码:

public int minNumberOperations(int[] target) {
    int res=target[0]; // 首位与左侧的高度差为自身高度
    for(int i=1;i<target.length;i++){
        if(target[i]>target[i-1]){ // 如果当前高度大于前一位
            res+=(target[i]-target[i-1]); // 累加高度差
        }
    }
    return res;
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 85.93% of Java online submissions for Minimum Number of Increments on Subarrays to Form a Target Array.

Memory Usage: 49 MB, less than 47.57% of Java online submissions for Minimum Number of Increments on Subarrays to Form a Target Array.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1526-minimum-number-of-increments-on-subarrays-to-form-a-target-array-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。