数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中将数组分成有序块的最大数量
假设我们给出一个数组 arr，它是 [0, 1, ..., arr.length - 1] 的排列，我们必须将数组分成几个“块”或分区，并分别对每个分区进行排序。因此，在连接它们之后，结果将是有序数组。如果数组类似于 [1,0,2,3,4]，则输出为 4，因为我们可以将其分成两个分区，例如 [1, 0] 和 [2,3,4]，但这也可以是 [1, 0]，[2]，[3]，[4]。这是可能的最高块数，因此输出为 4。
我们最多可以创建多少个块？
为了解决这个问题，我们将遵循以下步骤：
- ans := 0, minVal := inf, n := arr 的大小, maxVal := -inf
- 对于 i 从 0 到 n
- maxVal := arr[i] 和 maxVal 的最大值
- 如果 maxVal = i，则将 ans 加 1
- 返回 ans
示例
让我们来看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int ans = 0;
int minVal = INT_MAX;
int n = arr.size();
int maxVal = INT_MIN;
for(int i = 0; i < n; i++){
maxVal = max(arr[i], maxVal);
if(maxVal == i){
ans++;
}
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,0,2,3,4};
cout << (ob.maxChunksToSorted(v));
}输入
[1,0,2,3,4]
输出
4
更新于：2020年4月29日
396 次浏览
广告