Cho mảng A, chia thành left và right sao cho:
Mọi phần tử left ≤ mọi phần tử right
Left, right không rỗng
Left có kích thước nhỏ nhất
Tìm độ dài left. Ví dụ: [5,0,3,8,6] → 3 (left=[5,0,3], right=[8,6]).
Giải pháp:
Tính maxx[i] = max(A[0..i])
Duyệt từ phải sang trái, duy trì minVal = min(A[i..n-1])
Nếu minVal ≥ maxx[i-1] → ans = i (cập nhật nhỏ nhất)
Trả về ans
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: int partitionDisjoint(vector <int>& A) { int n = A.size(); vector <int> maxx(n); int minVal = A[n-1]; maxx[0] = A[0]; for(int i = 1; i < n; i++) maxx[i] = max(A[i], maxx[i-1]); int ans = n - 1; for(int i = n-1; i >= 1; i--){ minVal = min(minVal, A[i]); if(minVal >= maxx[i-1]) ans = i; } return ans; } }; int main(){ vector<int> v1 = {5,0,3,8,6}; Solution ob; cout << ob.partitionDisjoint(v1); }Đầu vào
[5,0,3,8,6]
Đầu ra
3