class Solution {
public:
int findMaximumLength(vector<int>& nums) {
}
};
100135. 找到最大非递减数组的长度
给你一个下标从 0 开始的整数数组 nums 。
你可以执行任意次操作。每次操作中，你需要选择一个 子数组 ，并将这个子数组用它所包含元素的 和 替换。比方说，给定数组是 [1,3,5,6] ，你可以选择子数组 [3,5] ，用子数组的和 8 替换掉子数组，然后数组会变为 [1,8,6] 。
请你返回执行任意次操作以后，可以得到的 最长非递减 数组的长度。
子数组 指的是一个数组中一段连续 非空 的元素序列。
示例 1：
输入：nums = [5,2,2] 输出：1 解释：这个长度为 3 的数组不是非递减的。 我们有 2 种方案使数组长度为 2 。 第一种，选择子数组 [2,2] ，对数组执行操作后得到 [5,4] 。 第二种，选择子数组 [5,2] ，对数组执行操作后得到 [7,2] 。 这两种方案中，数组最后都不是 非递减 的，所以不是可行的答案。 如果我们选择子数组 [5,2,2] ，并将它替换为 [9] ，数组变成非递减的。 所以答案为 1 。
示例 2：
输入：nums = [1,2,3,4] 输出：4 解释：数组已经是非递减的。所以答案为 4 。
示例 3：
输入：nums = [4,3,2,6] 输出：3 解释：将 [3,2] 替换为 [5] ，得到数组 [4,5,6] ，它是非递减的。 最大可能的答案为 3 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 105原站题解
python3 解法, 执行用时: 608 ms, 内存消耗: 36.5 MB, 提交时间: 2023-11-26 16:47:25
class Solution:
def findMaximumLength(self, nums: List[int]) -> int:
n = len(nums)
s = list(accumulate(nums, initial=0))
f = [0] * (n + 1)
last = [0] * (n + 1)
q = deque([0])
for i in range(1, n + 1):
# 去掉队首无用数据（计算转移直接取队首）
while len(q) > 1 and s[q[1]] + last[q[1]] <= s[i]:
q.popleft()
# 计算转移
f[i] = f[q[0]] + 1
last[i] = s[i] - s[q[0]]
# 去掉队尾无用数据
while q and s[q[-1]] + last[q[-1]] >= s[i] + last[i]:
q.pop()
q.append(i)
return f[n]
java 解法, 执行用时: 15 ms, 内存消耗: 54.9 MB, 提交时间: 2023-11-26 16:47:40
class Solution {
public int findMaximumLength(int[] nums) {
int n = nums.length;
long[] s = new long[n + 1];
int[] f = new int[n + 1];
long[] last = new long[n + 1];
int[] q = new int[n + 1]; // 数组模拟队列
int front = 0, rear = 0;
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + nums[i - 1];
// 去掉队首无用数据（计算转移直接取队首）
while (front < rear && s[q[front + 1]] + last[q[front + 1]] <= s[i]) {
front++;
}
// 计算转移
f[i] = f[q[front]] + 1;
last[i] = s[i] - s[q[front]];
// 去掉队尾无用数据
while (rear >= front && s[q[rear]] + last[q[rear]] >= s[i] + last[i]) {
rear--;
}
q[++rear] = i;
}
return f[n];
}
}
cpp 解法, 执行用时: 212 ms, 内存消耗: 150.3 MB, 提交时间: 2023-11-26 16:47:59
class Solution {
public:
int findMaximumLength(vector<int> &nums) {
int n = nums.size();
vector<long long> s(n + 1), last(n + 1);
vector<int> f(n + 1), q(n + 1); // 数组模拟队列
int front = 0, rear = 0;
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + nums[i - 1];
// 去掉队首无用数据（计算转移直接取队首）
while (front < rear && s[q[front + 1]] + last[q[front + 1]] <= s[i]) {
front++;
}
// 计算转移
f[i] = f[q[front]] + 1;
last[i] = s[i] - s[q[front]];
// 去掉队尾无用数据
while (rear >= front && s[q[rear]] + last[q[rear]] >= s[i] + last[i]) {
rear--;
}
q[++rear] = i;
}
return f[n];
}
};
golang 解法, 执行用时: 148 ms, 内存消耗: 10.5 MB, 提交时间: 2023-11-26 16:48:23
func findMaximumLength(nums []int) (ans int) {
n := len(nums)
s := make([]int, n+1)
f := make([]int, n+1)
last := make([]int, n+1)
q := []int{0}
for i := 1; i <= n; i++ {
s[i] = s[i-1] + nums[i-1]
// 去掉队首无用数据（计算转移直接取队首）
for len(q) > 1 && s[q[1]]+last[q[1]] <= s[i] {
q = q[1:]
}
// 计算转移
f[i] = f[q[0]] + 1
last[i] = s[i] - s[q[0]]
// 去掉队尾无用数据
for len(q) > 0 && s[q[len(q)-1]]+last[q[len(q)-1]] >= s[i]+last[i] {
q = q[:len(q)-1]
}
q = append(q, i)
}
return f[n]
}