Problem
Given an array A, partition it into two (contiguous) subarrays left and right so that:
- Every element in
leftis less than or equal to every element inright. leftandrightare non-empty.lefthas the smallest possible size.
Return the length of left after such a partitioning. It is guaranteed that such a partitioning exists.
Example 1:
Input: [5,0,3,8,6] Output: 3 Explanation: left = [5,0,3], right = [8,6]
Example 2:
Input: [1,1,1,0,6,12] Output: 4 Explanation: left = [1,1,1,0], right = [6,12]
Note:
2 <= A.length <= 300000 <= A[i] <= 10^6- It is guaranteed there is at least one way to partition
Aas described.
Solution 1: BST
Time complexity: O(nlogn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua, 100 ms class Solution { public: int partitionDisjoint(vector<int>& A) { multiset<int> s(begin(A) + 1, end(A)); int left_max = A[0]; for (int i = 1; i < A.size(); ++i) { if (*begin(s) >= left_max) return i; s.erase(s.equal_range(A[i]).first); left_max = max(left_max, A[i]); } return -1; } }; |
Solution 2: Greedy
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua, 28 ms class Solution { public: int partitionDisjoint(vector<int>& A) { int left_max = A[0]; int cur_max = A[0]; int left_len = 1; for (int i = 1; i < A.size(); ++i) { if (A[i] < left_max) { left_max = cur_max; left_len = i + 1; } else { cur_max = max(cur_max, A[i]); } } return left_len; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment