768. 最多能完成排序的块 II

题目描述

给你一个整数数组 arr 。

将 arr 分割成若干块，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

返回能将数组分成的最多块数？

示例 1：

输入：arr = [5,4,3,2,1]
输出：1
解释：
将数组分成2块或者更多块，都无法得到所需的结果。 
例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。

示例 2：

输入：arr = [2,1,3,4,4]
输出：4
解释：
可以把它分成两块，例如 [2, 1], [3, 4, 4]。 
然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。

提示：

1 <= arr.length <= 2000
0 <= arr[i] <= 10⁸

解法

方法一：单调栈

思考

数组可有重复，求最多切成多少块，使各块分别排序后整体有序。\(n\le 2000\)，枚举切点需快速判断「左侧都 \(\le\) 右侧」。

从左到右，已形成的块的最大值应单调不降。新值若小于栈顶，说明它必须并入前面某几块，弹出直到栈顶不大于它，再把原先的块最大值压回。

栈里留下的每个最大值对应一块，栈长即答案。

根据题目，我们可以发现，从左到右，每个分块都有一个最大值，并且这些分块的最大值呈单调递增（非严格递增）。我们可以用一个栈来存储这些分块的最大值。最后得到的栈的大小，也就是题目所求的最多能完成排序的块。

时间复杂度 \(O(n)\)，其中 \(n\) 表示 \(\textit{arr}\) 的长度。

Python3JavaC++GoTypeScriptRust

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        stk = []
        for v in arr:
            if not stk or v >= stk[-1]:
                stk.append(v)
            else:
                mx = stk.pop()
                while stk and stk[-1] > v:
                    stk.pop()
                stk.append(mx)
        return len(stk)

class Solution {
    public int maxChunksToSorted(int[] arr) {
        Deque<Integer> stk = new ArrayDeque<>();
        for (int v : arr) {
            if (stk.isEmpty() || stk.peek() <= v) {
                stk.push(v);
            } else {
                int mx = stk.pop();
                while (!stk.isEmpty() && stk.peek() > v) {
                    stk.pop();
                }
                stk.push(mx);
            }
        }
        return stk.size();
    }
}

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> stk;
        for (int& v : arr) {
            if (stk.empty() || stk.top() <= v)
                stk.push(v);
            else {
                int mx = stk.top();
                stk.pop();
                while (!stk.empty() && stk.top() > v) stk.pop();
                stk.push(mx);
            }
        }
        return stk.size();
    }
};

func maxChunksToSorted(arr []int) int {
    var stk []int
    for _, v := range arr {
        if len(stk) == 0 || stk[len(stk)-1] <= v {
            stk = append(stk, v)
        } else {
            mx := stk[len(stk)-1]
            stk = stk[:len(stk)-1]
            for len(stk) > 0 && stk[len(stk)-1] > v {
                stk = stk[:len(stk)-1]
            }
            stk = append(stk, mx)
        }
    }
    return len(stk)
}

function maxChunksToSorted(arr: number[]): number {
    const stk: number[] = [];
    for (let v of arr) {
        if (stk.length === 0 || v >= stk[stk.length - 1]) {
            stk.push(v);
        } else {
            let mx = stk.pop()!;
            while (stk.length > 0 && stk[stk.length - 1] > v) {
                stk.pop();
            }
            stk.push(mx);
        }
    }
    return stk.length;
}

impl Solution {
    pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
        let mut stk = Vec::new();
        for &v in arr.iter() {
            if stk.is_empty() || v >= *stk.last().unwrap() {
                stk.push(v);
            } else {
                let mut mx = stk.pop().unwrap();
                while let Some(&top) = stk.last() {
                    if top > v {
                        stk.pop();
                    } else {
                        break;
                    }
                }
                stk.push(mx);
            }
        }
        stk.len() as i32
    }
}

方法二：前缀最大值 + 后缀最小值

思考

单调栈没有显式表达切点条件。在 \(i\) 切开当且仅当前缀最大 \(\le\) 后缀最小。

预处理前缀最大，从右扫后缀最小，每处满足不等式则多一块。整段本身算一块，故初值 \(1\)。

我们希望将原始长度为 \(n\) 的数组划分为若干个区间，使得每个区间分别排序后，整体数组仍然有序。

考虑相邻两个区间：

左侧区间 left_chunk
右侧区间 right_chunk

若满足：

max(left_chunk) <= min(right_chunk)

则说明：

左侧区间中的任意元素都不会大于右侧区间中的任意元素
因此两个区间分别排序后，可以直接拼接成一个有序数组

于是，对于每个满足：

\[ 1 \le i < n \]

的索引 \(i\)，我们检查：

\[ \max(arr[:i]) \le \min(arr[i:]) \]

是否成立。

若成立，则说明索引 \(i\) 可以作为一个合法分割点。

为了快速计算上述条件，我们预处理：

prefix_maxs[j]表示：

\[ \max(arr[:j + 1]) \]

即前缀最大值。

suffix_min[j]表示：

\[ \min(arr[j:]) \]

即后缀最小值。

接下来：

从左到右遍历数组，计算所有前缀最大值
从右到左遍历数组，计算所有后缀最小值
对于每个索引 \(i\)，若：

prefix_maxs[i - 1] <= suffix_min[i]

成立，则说明：

左侧所有元素均不大于右侧所有元素
因此可以在索引 \(i\) 处分割数组

最终统计所有合法分割点数量即可。

注意：

即使数组严格递减，整个数组本身仍然可以视为一个合法区间。

因此数组能分成的最多块数为所有合法分割点数量 + \(1\)。

时间复杂度为 \(O(n)\)，空间复杂度为 \(O(n)\)，其中 \(n\) 表示 \(\textit{arr}\) 的长度。

Python3C++

class Solution:
    def maxChunksToSorted(self, arr: list[int]) -> int:
        prefix_maxs = []  # Max of each arr[:i + 1] where 0 <= i < len(arr).

        for num in arr:
            if not prefix_maxs:
                prefix_maxs.append(num)
                continue

            prefix_maxs.append(max(num, prefix_maxs[-1]))

        max_chunks = 1  # Base case.
        suffix_min = arr[-1]  # Min of arr[i:] where 0 <= i < len(arr).

        for idx in range(len(arr) - 1, 0, -1):
            if arr[idx] < suffix_min:
                suffix_min = arr[idx]

            if prefix_maxs[idx - 1] <= suffix_min:
                max_chunks += 1

        return max_chunks

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        vector<int> prefixMaxs; // Max of each arr[:i + 1]. 0 <= i < arr.size().

        for (const auto& num : arr) {
            if (prefixMaxs.empty()) {
                prefixMaxs.push_back(num);
                continue;
            }

            prefixMaxs.push_back(max(prefixMaxs.back(), num));
        }

        int maxChunks = 1; // Base case.
        int suffixMin = arr.back(); // Min of arr[i:]. 0 <= i < arr.size().

        for (int idx = arr.size() - 1; idx >= 1; idx--) {
            if (arr[idx] < suffixMin)
                suffixMin = arr[idx];

            if (prefixMaxs[idx - 1] <= suffixMin)
                maxChunks++;
        }

        return maxChunks;
    }
};

768. 最多能完成排序的块 II

题目描述

解法

方法一：单调栈

方法二：前缀最大值 + 后缀最小值

评论