Leetcode 1330:翻转子数组得到最大的数组值(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1330:翻转子数组得到最大的数组值(超详细的解法!!!)

in leetcode with 0 comment

给你一个整数数组 nums 。「 数组值」定义为所有满足 0 <= i < nums.length-1|nums[i]-nums[i+1]| 的和。

你可以选择给定数组的任意子数组,并将该子数组翻转。但你只能执行这个操作 一次

请你找到可行的最大 数组值

示例 1:

输入:nums = [2,3,1,5,4]
输出:10
解释:通过翻转子数组 [3,1,5] ,数组变成 [2,5,1,3,4] ,数组值为 10 。

示例 2:

输入:nums = [2,4,9,24,2,1,10]
输出:68

提示:

解题思路

我们可以假设子数组的区间在[i+1,j],那么反转前后只有i+1j位置的数组值会发生变化(取i+1的目的是便于处理)。反转前为|nums[i]-nums[i+1]|+|nums[j]-nums[j+1]|,反转后为|nums[i]-nums[j]|+|nums[i+1]-nums[j+1]|,那么我们的目的就是希望前后插值尽可能大。

有两个边界条件需要处理:1)恰好i+1位于数组nums的左边界。 2)恰好j位于数组nums的右边界。

class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        n, res, d = len(nums), 0, 0
        for i in range(n - 1):
            res += abs(nums[i] - nums[i + 1])

        for j in range(n - 1):
            for i in range(j):
                d = max(d, abs(nums[i] - nums[j]) + \
                        abs(nums[i + 1] - nums[j + 1]) - \
                        abs(nums[i] - nums[i + 1]) - \
                        abs(nums[j] - nums[j + 1]))
                
        for i in range(n - 1):
            d = max(d, abs(nums[i] - nums[-1]) - \
                        abs(nums[i] - nums[i + 1]))
        for j in range(n - 1):
            d = max(d, abs(nums[0] - nums[j + 1]) - \
                        abs(nums[j] - nums[j + 1]))
        return res + d

但是这么做会超时,所以我们需要优化。

设$a=nums[i],b=nums[i+1],c=nums[j],d=nums[j+1]$,此时交换$b$和$c$的位置,那么变化前后的差值就是

设$L[i]=min(a,b),H[i]=max(a,b),L[j]=min(c,d),H[j]=max(c,d)$,那么如果区间$[L[i],H[i]]$和区间$[L[j],H[j]]$相交。

L[i]---------------H[i]
         |          |
        L[j]----------------H[j]

那么此时交换$H[i]$和$L[j]$后

L[i]----H[i]
         |          |
                   L[j]-----H[j]

前后的变化$\delta = -区间的交集*2$。同理,如果区间$[L[i],H[i]]$和区间$[L[j],H[j]]$不相交的话,$\delta = 区间的交集*2$,所以我们现在的目标就是让L[j]-H[i]最大。

最后,需要考虑ij在边界的情况,在文章一开始的时候我们就提及过了。

class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        total, res, Hi, Lj = 0, 0, float('inf'), -float('inf')
        for a, b in zip(nums, nums[1:]):
            total += abs(a - b)
            Hi, Lj = min(Hi, max(a, b)), max(Lj, min(a, b))
            res = max(res, abs(nums[0] - b) - abs(a - b), \
                      abs(a - nums[-1]) - abs(a - b), \
                     (Lj - Hi) * 2)
        return total + res

reference:

https://leetcode.com/problems/reverse-subarray-to-maximize-array-value/discuss/489968/O(n)-Java-with-Mathematical-Proof

https://leetcode.com/problems/reverse-subarray-to-maximize-array-value/discuss/489743/JavaC%2B%2BPython-One-Pass-O(1)-Space

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses