5459. 形成目标数组的子数组最少增加次数 [hard]

第 31 场双周赛 https://leetcode-cn.com/contest/biweekly-contest-31

https://leetcode-cn.com/contest/biweekly-contest-31/problems/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

First Try

2020-07-25

周赛题目，没有做出来，看前几名的写法才知道还有这种解法。

重点是每个操作其实被限制在网上走1步，因此在往上走的时候，往上一步就需要一个操作；当往下走的时候，完全可以由前面往上走的覆盖掉，因此并不耗费操作。在往下走之后的重新往上走，需要重新开始统计，因为与前面另一个波峰的联系被谷底给切掉了。

有这个思路之后，就变成简单的计算递增的数量了。没想到一道hard题目，换个思路后可以这么简单。

class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        # 只有升序的时候需要考虑，降序都被之前处理掉了
        rv = target[0]  # 第一位总归要考虑进去
        for i in range(1, len(target)):
            rv += max(target[i] - target[i - 1], 0)
        return rv 

timeout try

其实按照递归写法也能解出来，画个图模拟下下沉的操作，每次遇到0的时候，就把左右变成孤岛各自努力。思路其实也没有问题，就是各种超时，案例都正确，但就是超时了。卡住的地方在于切割之后，无法快速的知道每个切割出来后的孤岛的最小值，想不出有什么数据结构可以快速完成这个需求。

下面这个解法是与下一个解法方向不同，不是往下沉，而是往上升的思路。一次性知道n个分割点，但是没用，还是超时了。

还是超时了
class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        
        rv = {"val": 0}
        cache = collections.defaultdict(list)
        for idx, t in enumerate(target):
            cache[t].append(idx)
        def opt(target, minv, lft, rt):
            if rt - lft == 1:
                rv["val"] += target[lft] - minv
                return target[lft]
            if lft >= rt:
                return 0 
            new_minv = min(target[lft: rt]) 
            rv["val"] += new_minv - minv
            boundaries = cache[new_minv]
            bdy = [b for b in boundaries if lft <= b < rt]
            # print(lft, rt, new_minv, bdy, rv["val"])
            for b in bdy:
                if b > lft:
                    opt(target, new_minv, lft, b)
                    lft = b
            opt(target, new_minv, b + 1, rt) # b + 1右边
            
        opt(target,0, 0, len(target))
        return rv["val"]

这个解法是按照下沉来考虑的，下沉到最小值之后，将数组切分为鼓励的岛屿，各自努力。查找最低点并进行切割的操作太繁琐，导致超时了。

# 超时了，oops
class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        
        rv = {"val": 0}
        def opt(target, lft, rt):
            if rt - lft == 1:
                rv["val"] += target[lft]
                return target[lft]
            if lft >= rt:
                return 0 
            minv = min(target[lft: rt])
            rv["val"] += minv 
            nlft = None 
            for i in range(lft, rt):
                target[i] -= minv 
                if target[i] > 0 and nlft is None:
                    nlft = i 
                elif target[i] == 0 and nlft is not None:
                    opt(target, nlft, i)
                    nlft = None 
            if nlft is not None:
                opt(target, nlft, rt)
        opt(target, 0, len(target))
        return rv["val"]

5459. 形成目标数组的子数组最少增加次数 [hard]​

First Try​

5459. 形成目标数组的子数组最少增加次数 [hard]

First Try