数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中将数组分成多个排序块的最大数量
假设我们有一个包含整数的数组 arr，我们需要将数组分成几个分区，并分别对每个分区进行排序。现在，在将它们连接起来后，我们将得到一个排序后的数组。我们需要找到我们可以创建的最大分区数？
因此，如果输入类似于 [3,2,4,5,5]，则输出将为 4，因为我们可以创建 [3,2]、[4]、[5]、[5] 这样的分区。
为了解决这个问题，我们将遵循以下步骤 -
cnt := 1
n := arr 的大小
定义一个大小为 n 的数组 maxOfLeft
定义一个大小为 n 的数组 minOfRight
maxOfLeft[0] := arr[0]
对于初始化 i := 1，当 i < n 时，更新（将 i 增加 1），执行 -
maxOfLeft[i] := maxOfLeft[i - 1] 和 arr[i] 中的最大值
minOfRight[n - 1] = arr[n - 1]
对于初始化 i := n - 2，当 i >= 0 时，更新（将 i 减小 1），执行 -
minOfRight[i] := minOfRight[i + 1] 和 arr[i] 中的最小值
对于初始化 i := 0，当 i < n - 1 时，更新（将 i 增加 1），执行 -
如果 minOfRight[i + 1] >= maxOfLeft[i]，则 -
(将 cnt 增加 1)
返回 cnt
让我们看看以下实现以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int cnt = 1;
int n = arr.size();
vector<int> maxOfLeft(n);
vector<int> minOfRight(n);
maxOfLeft[0] = arr[0];
for (int i = 1; i < n; i++)
maxOfLeft[i] = max(maxOfLeft[i - 1], arr[i]);
minOfRight[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
minOfRight[i] = min(minOfRight[i + 1], arr[i]);
for (int i = 0; i < n - 1; i++) {
if (minOfRight[i + 1] >= maxOfLeft[i])
cnt++;
}
return cnt;
}
};
main(){
Solution ob;
vector<int> v = {3,2,4,5,5};
cout << (ob.maxChunksToSorted(v));
}输入
{3,2,4,5,5}输出
4
更新于: 2020年6月8日
198 次查看
广告