Question

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

English Version

题目描述

给你一个整数数组 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] <= 108

解法

方法一：单调栈

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

时间复杂度 $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
  }
}