【2022-10-24每日一题】915. 分割数组[Medium]
2022-10-24
2分钟阅读时长
2022-10-24每日一题：915. 分割数组
难度：Medium
标签：数组
给定一个数组 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] <= 106- 可以保证至少有一种方法能够按题目所描述的那样对
nums进行划分。
方法一：两次遍历
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
func partitionDisjoint(nums []int) int {
n := len(nums)
// 处理后缀最小值
minRight := make([]int, n)
minRight[n-1] = nums[n-1]
for i := n-2; i > 0; i-- {
minRight[i] = min(minRight[i+1], nums[i])
}
maxLeft := nums[0]
for i := 1; ; i++ { // 题目保证有解，所以i到n-1之前一定可以找到答案
if maxLeft <= minRight[i] {
return i
}
maxLeft = max(maxLeft, nums[i])
}
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
时间复杂度：O(n)，其中 n 是 nums 的长度。求解 minRight 的时间复杂度是 O(n)，从前到后遍历 i 的时间复杂度也为 O(n)。
空间复杂度：O(n)，其中 n 是 nums 的长度。使用辅助数组 minRight 的空间开销为 O(n)。
方法二：一次遍历
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
func partitionDisjoint(nums []int) int {
n := len(nums)
leftMax, leftPos, curMax := nums[0], 0, nums[0]
for i := 1; i < n; i++ {
curMax = max(curMax, nums[i])
// 大于左侧最大值，需要处理
if nums[i] < leftMax {
leftMax, leftPos = curMax, i
}
}
return leftPos + 1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
时间复杂度：O(n)，其中 n 是 nums 的长度。从前到后遍历 i 的时间复杂度为 O(n)。
空间复杂度：O(1)。算法只使用了常数个变量。