class Solution {
public:
int partitionDisjoint(vector<int>& nums) {
}
};
915. 分割数组
给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：
left 中的每个元素都小于或等于 right 中的每个元素。left 和 right 都是非空的。left 的长度要尽可能小。在完成这样的分组后返回 left 的 长度 。
用例可以保证存在这样的划分方法。
示例 1：
输入：nums = [5,0,3,8,6] 输出：3 解释：left = [5,0,3]，right = [8,6]
示例 2：
输入：nums = [1,1,1,0,6,12] 输出：4 解释：left = [1,1,1,0]，right = [6,12]
提示：
2 <= nums.length <= 1050 <= nums[i] <= 106nums 进行划分。原站题解
python3 解法, 执行用时: 192 ms, 内存消耗: 25.4 MB, 提交时间: 2022-10-24 11:18:04
class Solution:
def partitionDisjoint(self, nums: List[int]) -> int:
'''
一次遍历
'''
n = len(nums)
cur_max = left_max = nums[0]
left_pos = 0
for i in range(1, n - 1):
cur_max = max(cur_max, nums[i])
if nums[i] < left_max:
left_max, left_pos = cur_max, i
return left_pos + 1
python3 解法, 执行用时: 312 ms, 内存消耗: 25.5 MB, 提交时间: 2022-10-24 11:15:02
class Solution:
def partitionDisjoint(self, nums: List[int]) -> int:
'''
两次遍历, maxLeft <= minRight
'''
n = len(nums)
min_right = [0] * n
min_right[-1] = nums[-1] # 右边至少有一个数
for i in range(n - 2, 0, -1):
min_right[i] = min(min_right[i + 1], nums[i]) # min_right 顺序排序
max_left = nums[0]
for i in range(1, n):
if max_left <= min_right[i]:
return i
max_left = max(max_left, nums[i])