跳转至

3511. 构造正数组 🔒

题目描述

给定一个数组 nums。一个数组被认为是 正 的，如果每个包含 超过两个 元素的 子数组 的所有数字之和都是正数。

您可以执行以下操作任意多次：

  • 用 -1018 和 1018 之间的任意整数替换 nums 中的 一个 元素。

找到使 nums 变为正数组所需的最小操作数。

 

示例 1：

输入：nums = [-10,15,-12]

输出：1

解释：

唯一有超过 2 个元素的子数组是这个数组本身。所有元素的和是 (-10) + 15 + (-12) = -7。通过将 nums[0] 替换为 0，新的和变为 0 + 15 + (-12) = 3。因此，现在数组是正的。

示例 2：

输入：nums = [-1,-2,3,-1,2,6]

输出：1

解释：

具有 2 个以上元素且和非正的子数组是：

子数组下标 子数组 和 替换后的子数组（令 nums[1] = 1） 新的和
nums[0...2] [-1, -2, 3] 0 [-1, 1, 3] 3
nums[0...3] [-1, -2, 3, -1] -1 [-1, 1, 3, -1] 2
nums[1...3] [-2, 3, -1] 0 [1, 3, -1] 3

因此，nums 在一次操作后是正的。

示例 3：

输入：nums = [1,2,3]

输出：0

解释：

数组已经是正的，所以不需要操作。

 

提示：

  • 3 <= nums.length <= 105
  • -109 <= nums[i] <= 109

解法

方法一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def makeArrayPositive(self, nums: List[int]) -> int:
        l = -1
        ans = pre_mx = s = 0
        for r, x in enumerate(nums):
            s += x
            if r - l > 2 and s <= pre_mx:
                ans += 1
                l = r
                pre_mx = s = 0
            elif r - l >= 2:
                pre_mx = max(pre_mx, s - x - nums[r - 1])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int makeArrayPositive(int[] nums) {
        int ans = 0;
        long preMx = 0, s = 0;
        for (int l = -1, r = 0; r < nums.length; r++) {
            int x = nums[r];
            s += x;
            if (r - l > 2 && s <= preMx) {
                ans++;
                l = r;
                preMx = s = 0;
            } else if (r - l >= 2) {
                preMx = Math.max(preMx, s - x - nums[r - 1]);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int makeArrayPositive(vector<int>& nums) {
        int ans = 0;
        long long preMx = 0, s = 0;
        for (int l = -1, r = 0; r < nums.size(); r++) {
            int x = nums[r];
            s += x;
            if (r - l > 2 && s <= preMx) {
                ans++;
                l = r;
                preMx = s = 0;
            } else if (r - l >= 2) {
                preMx = max(preMx, s - x - nums[r - 1]);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func makeArrayPositive(nums []int) (ans int) {
    l := -1
    preMx := 0
    s := 0
    for r, x := range nums {
        s += x
        if r-l > 2 && s <= preMx {
            ans++
            l = r
            preMx = 0
            s = 0
        } else if r-l >= 2 {
            preMx = max(preMx, s-x-nums[r-1])
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function makeArrayPositive(nums: number[]): number {
    let l = -1;
    let [ans, preMx, s] = [0, 0, 0];
    for (let r = 0; r < nums.length; r++) {
        const x = nums[r];
        s += x;
        if (r - l > 2 && s <= preMx) {
            ans++;
            l = r;
            preMx = 0;
            s = 0;
        } else if (r - l >= 2) {
            preMx = Math.max(preMx, s - x - nums[r - 1]);
        }
    }
    return ans;
}

评论