Java C++题解leetcode769最多能完成排序的块
题目要求
思路：模拟
Java
class Solution {
public int maxChunksToSorted(int[] arr) {
int n = arr.length, res = 0;
int min = n, max = -1;
for (int r = 0, l = 0; r < n; r++) {
min = Math.min(min, arr[r]);
max = Math.max(max, arr[r]);
if (l == min && r == max) {
res++;
l = r + 1;
min = n;
}
}
return res;
}
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)
再改进【拜题设限制所赐】
手推一遍上面的执行过程发现最小值没有什么意义，可以只用最大值衡量，找一个区间右端点rrr，这个r与arr在[0,r]内的最大值相等；
- 从头开始统计当前向前区间内的最大值，若该值与遍历下标相等，则块满足题设条件，答案加一；
- 然后无需进行归零，因为后续的所有值一定都大于当前块的最大值；
- 重复遍历与比较。
之所以可以省略最小值的统计，是因为块的大小由最大值决定，小的值都在前面的块里被排序，所以一定能在当前块找到一个与左端点相等的值（最小值）；
- 此外，当前统计到的最大值既是当前区间内的最大值，也是arr从头至此的最大值。
class Solution {
public int maxChunksToSorted(int[] arr) {
int res = 0, max = -1;
for (int r = 0; r < arr.length; r++) {
max = Math.max(max, arr[r]);
if (r == max)
res++;
}
return res;
}
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)
C++
- 第一万次注意max变量和max方法的命名冲突……
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int res = 0, maxx = -1;
for (int r = 0; r < arr.size(); r++) {
maxx = max(maxx, arr[r]);
if (r == maxx)
res++;
}
return res;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
Rust
impl Solution {
pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
let (mut res, mut maxx) = (0, -1);
for r in 0..arr.len() {
maxx = maxx.max(arr[r]);
if r as i32 == maxx {
res += 1;
}
}
res
}
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)
总结
- 简单到没什么好总结的……题设的限制极大地降低了题目难度，本来看题还没有意识到，看到示例就意识到了今天可以拥有简单题的快乐~
- 看官方的题解管这个再改进方法叫贪心，分析了好长好长……看着就头疼
- 还有其他解法用栈的，本质上思路一样，是理解比较浅但实现稍复杂的方法。
以上就是Java C++题解LeetCode769最多能完成排序的块的详细内容，更多关于Java C++最多能完成排序的块的资料请关注其它相关文章！
相关文章