Giả sử chúng ta có một mảng arr các số nguyên, chúng ta phải chia mảng thành một số phân vùng, và sắp xếp riêng từng phân vùng. Sau khi nối chúng lại, chúng ta sẽ nhận được một mảng đã sắp xếp. Chúng ta phải tìm số lượng phân vùng tối đa chúng ta có thể tạo?
Vì vậy, nếu đầu vào giống như [3,2,4,5,5], thì đầu ra sẽ là 4, vì chúng ta có thể tạo các phân vùng như [3,2], [4], [5], [5].
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
cnt := 1
n := kích thước của arr
Định nghĩa mảng maxOfLeft kích thước n
Định nghĩa mảng minOfRight kích thước n
maxOfLeft[0] := arr[0]
for khởi tạo i := 1, khi i < n, cập nhật (tăng i lên 1), thực hiện −
maxOfLeft[i] := max của maxOfLeft[i - 1] và arr[i]
minOfRight[n - 1] = arr[n - 1]
for khởi tạo i := n - 2, khi i >= 0, cập nhật (giảm i xuống 1), thực hiện −
minOfRight[i] := min của minOfRight[i + 1] và arr[i]
for khởi tạo i := 0, khi i < n - 1, cập nhật (tăng i lên 1), thực hiện −
nếu minOfRight[i + 1] >= maxOfLeft[i], thì −
(tăng cnt lên 1)
trả về cnt
Hãy xem triển khai sau để hiểu rõ hơn −
Ví dụ
#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)); } Đầu vào
{3,2,4,5,5} Đầu ra
4