Loading... # 分割数组的最大值 这道题粗看没有任何的思路，看了题解感觉解法真的是很妙，利用二分和自定义的上下界条件等，获得了最终的答案。 首先是上下界的定义，我们可以知道子数组各自的和的最小值是单个元素，也就是分割的数组个数等于数组长度，而最大值就是不分割的和。 于是 lo = max(nums)，hi = sum(nums) 然后在这个界限中，可以利用二分找到 k 个子数组各自和最大值的最小，我们可以计算让每个子数组都小于 mid 需要多少个子数组，作为 cnt，这样便能通过 cnt 来判断二分的收缩条件。 $ cnt > k 则 lo = mid + 1$ $ cnt <= k 则 hi = mid$ 这样最终得到的 lo 即为答案 ```go func splitArray(nums []int, k int) int { lo, hi := 0, 0 for _, v := range nums { if v > lo { lo = v } hi += v } for lo < hi { mid := lo + ((hi - lo) >> 1) sum, cnt := 0, 1 for _, v := range nums { if sum + v > mid { sum = v cnt++ } else { sum += v } } // 分段需要超过k段才能达到mid值，说明达不到，lo扩展 if cnt > k { lo = mid + 1 } else { hi = mid } } return lo } ``` # 寻找峰值 二分变形 ```go func findPeakElement(nums []int) int { l, r := 0, len(nums)-1 for l < r { mid := l + (r - l) / 2 if nums[mid] < nums[mid+1] { l = mid + 1 } else { r = mid } } return l // or nums[l] } ``` # 库存管理 也是个二分变形，有重复元素，所以不能像寻找峰值一样做 ```go func inventoryManagement(stock []int) int { l, r := 0, len(stock)-1 for l < r { mid := l + ((r - l) >> 1) if stock[mid] > stock[r] { l = mid + 1 } else if stock[mid] < stock[r] { r = mid } else { r-- } } return stock[l] } ``` # 寻找两个正序数组的中位数 这道题我们把两个数组都分成左边和右边，然后把两个数组的左边看成是一个数组，右边看成是一个数组，且`左边数组的大小=右边数组的大小` 或 `左边数组的大小+1=右边数组的大小`。 然后在这个前提下，左边的数组最大值满足小于等于右边的数组最小值，那么中位数就很容易得出了。 要么左边数组比右边数组大，那么就是左边的两个数组中最大的那个是中位数。 要么左边数组等于右边数组，那么就是左边的两个数组中最大的和右边两个数组中最小的加起来除以二，就是中位数。 所以我们可以知道左边数组的长度为 (n + m + 1) / 2，作为 leftTotal，对长度较小的数组进行二分，取一个位置 i，那么另一个数组的左半部分就是 leftTotal - i，作为 j 那么我们需要的是 $nums1[i-1] <= nums2[j]\ \&\&\ nums2[j-1] <= nums1[i]$ 如果不满足以上条件，存在 nums1[i-1] > nums2[j]，说明目前切分的位置应该向左挪，否则应该向右挪动。 所以得到二分实现代码如下： ```go func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { if len(nums1) > len(nums2) { return findMedianSortedArrays(nums2, nums1) } m, n := len(nums1), len(nums2) leftTotal := (m + n + 1) / 2 l, r := 0, m for l <= r { i := (l + r) / 2 j := leftTotal - i ALeft := math.Inf(-1) if i > 0 { ALeft = float64(nums1[i-1]) } ARight := math.Inf(1) if i < m { ARight = float64(nums1[i]) } BLeft := math.Inf(-1) if j > 0 { BLeft = float64(nums2[j-1]) } BRight := math.Inf(1) if j < n { BRight = float64(nums2[j]) } if ALeft <= BRight && BLeft <= ARight { if (m+n)%2 == 1 { return math.Max(ALeft, BLeft) } else { return (math.Max(ALeft, BLeft) + math.Min(ARight, BRight)) / 2 } } else if ALeft > BRight { r = i - 1 } else { l = i + 1 } } return -1 // 不会走到这里 } ``` # x的平方根 这道题也是简单的二分法，但是需要考虑特殊的上下界，这里应取r的值，用l=0, r=x/2作为区间。 ```go func mySqrt(x int) int { if x < 2 { return x } l, r := 0, x/2 for l <= r { mid := l + ((r-l)>>1) if mid * mid == x { return mid } if mid * mid > x { r = mid-1 } else { l = mid+1 } } return r } ``` Last modification：July 20, 2025 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 如果觉得我的文章对你有用，请随意赞赏
