LeetCode 915. 分割数组

Categories:

题目描述
思路分析
1. 解法一：前缀最大 + 后缀最小（推荐）
相似题目

题目描述

✅ 915. 分割数组

思路分析

解法一：前缀最大 + 后缀最小（推荐）

核心思路：

leftMax[i] 表示 0..i 的最大值，rightMin[i] 表示 i..n-1 的最小值。

找到最小的 i 满足 leftMax[i] <= rightMin[i+1]。

分割点为 i + 1。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，需要两个辅助数组。

class Solution {
    public int partitionDisjoint(int[] nums) {
        int n = nums.length;
        int[] leftMax = new int[n];
        int[] rightMin = new int[n];

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

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

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

        return n;
    }
}

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++ {
		if nums[i] > leftMax[i-1] {
			leftMax[i] = nums[i]
		} else {
			leftMax[i] = leftMax[i-1]
		}
	}

	rightMin[n-1] = nums[n-1]
	for i := n - 2; i >= 0; i-- {
		if nums[i] < rightMin[i+1] {
			rightMin[i] = nums[i]
		} else {
			rightMin[i] = rightMin[i+1]
		}
	}

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

	return n
}

相似题目

题目	难度	考察点
769. 最多能完成排序的块	中等	前缀最大
768. 最多能完成排序的块 II	困难	前缀最大
238. 除自身以外数组的乘积	中等	前后缀
915. 分割数组	中等	前后缀
1438. 绝对差不超过限制的最长连续子数组	中等	双端队列

本文作者: HGNULB

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