数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究通过最多 K 次递增操作使元素相等的子数组的最长长度
在这个问题中，我们将找到最长子数组的长度，以便我们可以通过添加一些正整数的值来使所有子数组元素相同，并且添加到每个元素的数字之和不应超过 K。
朴素的方法是找到在给定数组的每个子数组中使所有元素相同所需的成本。最后，考虑成本小于 K 且长度最大的子数组的长度。
但是，我们将使用队列数据结构来有效地解决这个问题。
问题陈述 - 我们给定一个包含整数的 N 个大小的数组。此外，我们还给定一个正整数 K。任务是找到最长子数组的长度，以便我们可以通过向子数组的每个元素添加一些数字来使所有子数组元素相同。此外，添加的数字之和不应超过 K。
示例
输入
K = 6; arr[] = {2, 3, 5, 15, 3, 8};
输出
3
解释 - 我们可以取子数组 {2, 3, 5}。因此，使子数组所有元素相等的总成本是 {3, 2, 0} 的和，即 5。
输入
K = 2; arr[] = {2, 2, 2, 2, 2, 2}
输出
6
解释 - 给定数组的所有元素都相同。因此，我们可以选择给定数组作为子数组。
输入
K = 3; arr[] = {4, 5, 4, 4, 5, 1, 2, 3, 3, 3};
输出
5
解释 - 在这里，我们可以选择子数组 {4, 5, 4, 4, 5} 或 {1, 2, 3, 3, 3}，因为这两个数组具有相同的长度，并且使所有数字相等的成本都等于 3。
方法 1
在这种方法中，我们将遍历给定数组的所有子数组。此外，我们将跟踪当前子数组的最大元素和元素之和。如果使子数组所有元素相等的成本小于 K，并且其长度小于 max_len，我们将更新 max_len。
算法
步骤 1 - 定义 max_len 并初始化为 0
步骤 2 - 使用循环开始遍历数组。在循环中，定义 maxEle 和 sum 变量，并将它们初始化为 0。
步骤 3 - 使用另一个嵌套循环从第 P 个索引遍历数组，因为子数组从第 P 个索引开始。
步骤 4 - 如果它小于当前数组元素，则更新 maxEle。此外，将数组元素添加到“sum”变量。
步骤 5 - 现在，我们需要使子数组的所有元素等于 maxEle，子数组的长度为 q − p + 1。因此，如果 maxEle * (q − p + 1) 小于或等于 K，如果它小于 q − p + 1，则更新 max_len 变量。
步骤 6 - 返回 max_len 值。
示例
#include <bits/stdc++.h>
using namespace std;
int maxSubArrayLength(int arr[], int N, int K) {
int max_len = 0;
// Traverse all subarrays of the given array
for (int p = 0; p < N; p++) {
int maxEle = 0;
int sum = 0;
for (int q = p; q < N; q++) {
// Update maximum element
maxEle = max(maxEle, arr[q]);
sum += arr[q];
// Check whether we can make all elements of the array equal to maxEle
if (maxEle * (q - p + 1) <= sum + K) {
// Update maximum length
max_len = max(max_len, q - p + 1);
}
}
}
return max_len;
}
int main() {
int N = 6;
int K = 6;
int arr[] = {2, 3, 5, 15, 3, 8};
cout << "The maximum length of subarray such that we can make all elements of it same is " << maxSubArrayLength(arr, N, K);
return 0;
}
输出
The maximum length of subarray such that we can make all elements of it same is 3
时间复杂度 - O(N*N)，遍历所有子数组。
空间复杂度 - O(1)
方法 2
算法
步骤 1 - 定义名为“maxQueue”的双端队列数据结构，用于存储子数组的最大元素的索引。
步骤 2 - 定义 pref_sum[] 数组以存储前缀和，并将第 0 个索引初始化为 0。
步骤 3 - 遍历数组并将元素的前缀和存储到 pref_sum[] 数组中。
步骤 4 - 将“left”和“max_len”初始化为 0，指向数组的左索引并跟踪子数组的最大长度。此外，定义 max_ele 来存储子数组的最大元素。
步骤 5 - 再次开始遍历数组。
步骤 5.1 - 在 for 循环中，使用 while 循环从队列中移除元素，直到队列为空或队列最后一个索引处的元素小于 arr[p]。
步骤 5.2 - 将 p 插入队列。
步骤 5.3 - 如果 p 为 0，则将 max_ele 初始化为 arr[p]。否则，仅当它小于 arr[p] 时才更新 max_ele。
步骤 5.4 - 现在使用 while 循环进行迭代，直到 (p − left + 1) * max_ele − (pref_sum[p + 1] − pref_sum[left] 大于 K，或“left”点小于 p。
步骤 5.4.1 - 在 while 循环中，每次迭代将“left”递增 1。
步骤 5.4.2 - 此外，删除小于“left”的队列元素。
步骤 5.5 - 如果它大于 max_len，则使用 p − left + 1 更新 max_len。
步骤 6 - 返回 max_len 值。
示例
#include <bits/stdc++.h>
using namespace std;
int maxSubArrayLength(int arr[], int N, int K) {
// Queue to store elements
deque<int> maxQueue;
// To store prefix sum
int pref_sum[N + 1];
pref_sum[0] = 0;
// Calculating the prefix sum
for (int p = 1; p <= N; p++) {
pref_sum[p] = pref_sum[p - 1] + arr[p - 1];
}
// Start point of sub-array
int left = 0;
// For tracking the maximum element of the sub-array
int max_ele;
// To store the answer
int max_len = 0;
for (int p = 0; p < N; p++) {
// Remove all smaller elements from the back to make the current element as maximum
while (!maxQueue.empty() && arr[maxQueue.back()] < arr[p]) {
maxQueue.pop_back();
}
// Insert current index
maxQueue.push_back(p);
// Update maximum element
if (p == 0) {
max_ele = arr[p];
} else
max_ele = max(max_ele, arr[p]);
// Calculating the cost to make all elements equal to the maximum
while ((p - left + 1) * max_ele - (pref_sum[p + 1] - pref_sum[left]) > K && p > left) {
// Increment starting point
left++;
// Remove the element from the current window
while (!maxQueue.empty() && maxQueue.front() < left && left < p) {
maxQueue.pop_front();
max_ele = arr[maxQueue.front()];
}
}
// Update maximum size
max_len = max(max_len, p - left + 1);
}
return max_len;
}
int main() {
int N = 6;
int K = 6;
int arr[] = {2, 3, 5, 15, 3, 8};
cout << "The maximum length of subarray such that we can make all elements of it same is " << maxSubArrayLength(arr, N, K);
return 0;
}
输出
The maximum length of subarray such that we can make all elements of it same is 3
时间复杂度 - O(N^2)，因为我们使用嵌套循环。
空间复杂度 - O(N)，因为我们使用队列。
在最坏情况下，两种方法的时间复杂度相同。但是，当我们需要对常规数组执行给定操作时，第二种方法更高效。
324 次浏览
