代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
这个问题和“最多能完成排序的块”相似，但给定数组中的元素可以重复，输入数组最大长度为2000，其中的元素最大为10**8。
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] 可以得到最多的块数。
注意:
arr的长度在[1, 2000]之间。arr[i]的大小在[0, 10**8]之间。方法一：单调栈
根据题目，我们可以发现，从左到右，每个分块都有一个最大值，并且这些分块的最大值呈单调递增（非严格递增）。我们可以用一个栈来存储这些分块的最大值。最后得到的栈的大小，也就是题目所求的最多能完成排序的块。
时间复杂度 $O(n)$，其中 $n$ 表示 $arr$ 的长度。
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 stack = [];
for (const num of arr) {
if (stack.length !== 0 && num < stack[stack.length - 1]) {
const max = stack.pop();
while (stack.length !== 0 && num < stack[stack.length - 1]) {
stack.pop();
}
stack.push(max);
} else {
stack.push(num);
}
}
return stack.length;
}
impl Solution {
pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
let mut stack = vec![];
for num in arr.iter() {
if !stack.is_empty() && num < stack.last().unwrap() {
let max = stack.pop().unwrap();
while !stack.is_empty() && num < stack.last().unwrap() {
stack.pop();
}
stack.push(max)
} else {
stack.push(*num);
}
}
stack.len() as i32
}
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。