Question

769. Max Chunks To Make Sorted

中文文档

Description

You are given an integer array arr of length n that represents a permutation of the integers in the range [0, n - 1].

We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.

Return _the largest number of chunks we can make to sort the array_.

 

Example 1:

Input: arr = [4,3,2,1,0]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.

Example 2:

Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

 

Constraints:

• n == arr.length
• 1 <= n <= 10
• 0 <= arr[i] < n
• All the elements of arr are unique.

Solutions

Solution 1

class Solution:
  def maxChunksToSorted(self, arr: List[int]) -> int:
    mx = ans = 0
    for i, v in enumerate(arr):
      mx = max(mx, v)
      if i == mx:
        ans += 1
    return ans

class Solution {
  public int maxChunksToSorted(int[] arr) {
    int ans = 0, mx = 0;
    for (int i = 0; i < arr.length; ++i) {
      mx = Math.max(mx, arr[i]);
      if (i == mx) {
        ++ans;
      }
    }
    return ans;
  }
}

class Solution {
public:
  int maxChunksToSorted(vector<int>& arr) {
    int ans = 0, mx = 0;
    for (int i = 0; i < arr.size(); ++i) {
      mx = max(mx, arr[i]);
      ans += i == mx;
    }
    return ans;
  }
};

func maxChunksToSorted(arr []int) int {
  ans, mx := 0, 0
  for i, v := range arr {
    mx = max(mx, v)
    if i == mx {
      ans++
    }
  }
  return ans
}

function maxChunksToSorted(arr: number[]): number {
  const n = arr.length;
  let ans = 0;
  let max = 0;
  for (let i = 0; i < n; i++) {
    max = Math.max(arr[i], max);
    if (max == i) {
      ans++;
    }
  }
  return ans;
}

impl Solution {
  pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
    let mut res = 0;
    let mut max = 0;
    for i in 0..arr.len() {
      max = max.max(arr[i]);
      if max == (i as i32) {
        res += 1;
      }
    }
    res
  }
}

#define max(a, b) (((a) > (b)) ? (a) : (b))

int maxChunksToSorted(int* arr, int arrSize) {
  int res = 0;
  int mx = -1;
  for (int i = 0; i < arrSize; i++) {
    mx = max(mx, arr[i]);
    if (mx == i) {
      res++;
    }
  }
  return res;
}

Solution 2

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() || v >= stk.peek()) {
        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() || v >= stk.top()) {
        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 {
  stk := []int{}
  for _, v := range arr {
    if len(stk) == 0 || v >= stk[len(stk)-1] {
      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)
}