LeetCode 915. 分割数组

Categories:

题目描述
思路分析
参考代码

题目描述

🔥 915. 分割数组

思路分析

要解决这个问题，你可以使用前缀最大值和后缀最小值的方法。

首先，你可以计算数组中每个位置的前缀最大值和后缀最小值。

然后，遍历数组，找到第一个位置，使得前缀最大值小于等于后缀最小值。这个位置将是 left 和 right 分界点。

参考代码

func partitionDisjoint(nums []int) int {
	n := len(nums)
	leftMax := make([]int, n)
	rightMin := make([]int, n)

	leftMax[0] = nums[0]
	for i := 1; i < n; i++ {
		leftMax[i] = max(leftMax[i-1], nums[i])
	}

	rightMin[n-1] = nums[n-1]
	for i := n - 2; i >= 0; i-- {
		rightMin[i] = min(rightMin[i+1], nums[i])
	}

	for i := 0; i < n-1; i++ {
		if leftMax[i] <= rightMin[i+1] {
			return i + 1
		}
	}
	return -1
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/48975607