单调栈、排序哈希映射 2 算法,slice() / Arrays.copyOfRange / Arrays.Copy / append([]int{}, ar...) / memcpy 拷贝数组,求解《768. 最多能完成排序的块 II》

例题

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

这个问题和“最多能完成排序的块”相似,但给定数组中的元素可以重复,输入数组最大长度为2000,其中的元素最大为1e8。
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, 1e8]之间。

答案

单调栈

var maxChunksToSorted = function(arr) {
  const n = arr.length, monotoneStack = []
  for (let i = 0; i < n; i++) {
    if (monotoneStack.length === 0 || arr[i] >= monotoneStack[monotoneStack.length - 1]) {
      monotoneStack.push(arr[i])
    } else {
      const maxNum = monotoneStack.pop()
      while (monotoneStack.length > 0 && arr[i] < monotoneStack[monotoneStack.length - 1]) {
        monotoneStack.pop()
      }
      monotoneStack.push(maxNum)
    }
  }
  return monotoneStack.length
};
function maxChunksToSorted(arr: number[]): number {
  const n = arr.length, monotoneStack = []
  for (let i = 0; i < n; i++) {
    if (monotoneStack.length === 0 || monotoneStack[monotoneStack.length - 1] <= arr[i]) {
      monotoneStack.push(arr[i])
    } else {
      const maxNum = monotoneStack.pop()
      while (monotoneStack.length && monotoneStack[monotoneStack.length - 1] > arr[i]) monotoneStack.pop()
      monotoneStack.push(maxNum)
    }
  }
  return monotoneStack.length
};
class Solution {
  function maxChunksToSorted($arr) {
    $monotoneStack = [];
    foreach($arr as $num) {
      if (count($monotoneStack) === 0 || end($monotoneStack) <= $num) {
        $monotoneStack []= $num;
      } else {
        $maxNum = array_pop($monotoneStack);
        while (count($monotoneStack) > 0 && end($monotoneStack) > $num) {
          array_pop($monotoneStack);
        }
        $monotoneStack []= $maxNum;
      }
    }
    return count($monotoneStack);
  }
}
func maxChunksToSorted(arr []int) int {
  monotoneStack := []int{}
  for _, num := range arr {
    if len(monotoneStack) == 0 || monotoneStack[len(monotoneStack) - 1] <= num {
      monotoneStack = append(monotoneStack, num)
    } else {
      maxNum := monotoneStack[len(monotoneStack) - 1]
      monotoneStack = monotoneStack[:len(monotoneStack) - 1]
      for len(monotoneStack) > 0 && monotoneStack[len(monotoneStack) - 1] > num {
        monotoneStack = monotoneStack[:len(monotoneStack) - 1]
      }
      monotoneStack = append(monotoneStack, maxNum)
    }
  }
  return len(monotoneStack)
}
class Solution {
  public int maxChunksToSorted(int[] arr) {
    Deque<Integer> monotoneStack = new ArrayDeque<Integer>();
    for (int num : arr) {
      if (monotoneStack.isEmpty() || monotoneStack.peek() <= num) {
        monotoneStack.push(num);
      } else {
        int maxNum = monotoneStack.pop();
        while (monotoneStack.isEmpty() == false && monotoneStack.peek() > num) monotoneStack.pop();
        monotoneStack.push(maxNum);
      }
    }
    return monotoneStack.size();
  }
}
public class Solution {
  public int MaxChunksToSorted(int[] arr) {
    Stack<int> monotoneStack = new Stack<int>();
    foreach (int num in arr) {
      if (monotoneStack.Count == 0 || monotoneStack.Peek() <= num) {
        monotoneStack.Push(num);
      } else {
        int maxNum = monotoneStack.Pop();
        while (monotoneStack.Count > 0 && monotoneStack.Peek() > num) monotoneStack.Pop();
        monotoneStack.Push(maxNum);
      }
    }
    return monotoneStack.Count;
  }
}
int maxChunksToSorted(int* arr, int arrSize){
  int* monotoneStack = malloc(sizeof(int) * 2000);
  int p = 0;
  for (int i = 0; i < arrSize; i++) {
    if (p == 0 || monotoneStack[p - 1] <= arr[i]) monotoneStack[p++] = arr[i];
    else {
      int maxNum = monotoneStack[--p];
      while (p > 0 && monotoneStack[p - 1] > arr[i]) p--;
      monotoneStack[p++] = maxNum; 
    }
  }
  return p;
}
class Solution {
public:
  int maxChunksToSorted(vector<int>& arr) {
    stack<int> monotoneStack;
    for (int num : arr) {
      if (monotoneStack.empty() || monotoneStack.top() <= num) monotoneStack.push(num);
      else {
        int maxNum = monotoneStack.top();
        monotoneStack.pop();
        while (monotoneStack.empty() == false && monotoneStack.top() > num) monotoneStack.pop();
        monotoneStack.push(maxNum);
      }
    }
    return monotoneStack.size();
  }
};
class Solution:
  def maxChunksToSorted(self, arr: List[int]) -> int:
    monotoneStack = []
    for num in arr:
      if len(monotoneStack) == 0 or monotoneStack[-1] <= num: monotoneStack.append(num)
      else:
        maxNum = monotoneStack.pop()
        while len(monotoneStack) > 0 and monotoneStack[-1] > num: monotoneStack.pop()
        monotoneStack.append(maxNum)
    return len(monotoneStack)

排序 · 哈希映射

var maxChunksToSorted = function(arr) {
  const n = arr.length, h = new Map, a = arr.slice().sort((a, b) => a - b)
  let r = 0
  for (let i = 0; i < n; i++) {
    add(h, arr[i], 1)
    add(h, a[i], -1)
    if (h.size === 0) r++
  }
  return r
};
function add(h, k, v) {
  v += h.get(k) || 0
  if (v === 0) h.delete(k)
  else h.set(k, v)
}
function maxChunksToSorted(arr: number[]): number {
  const n = arr.length, h = {c:Object.create(null), size: 0}, a = arr.slice().sort((a, b) => a - b)
  let r = 0
  for (let i = 0; i < n; i++) {
    add(h, arr[i], 1)
    add(h, a[i], -1)
    if (h.size === 0) r++
  }
  return r
};
function add(h: {c: Object, size: number}, k: number, v: number) {
  if (h.c[k] === void 0) {
    h.size++
    h.c[k] = v
  } else {
    h.c[k] += v
    if (h.c[k] === 0) {
      delete h.c[k]
      h.size--
    }
  }
}
class Solution {
  private $h = [];
  function maxChunksToSorted($arr) {
    $a = $arr;
    usort($a, function($a, $b) {
      return $a > $b;
    });
    $n = count($arr);
    $r = 0;
    for ($i = 0; $i < $n; $i++) {
      $this->add($a[$i], 1);
      $this->add($arr[$i], -1);
      if (count($this->h) == 0) $r++;
    }
    return $r;
  }
  function add($k, $v) {
    $v += $this->h[$k] ?? 0;
    if ($v === 0) unset($this->h[$k]);
    else $this->h[$k] = $v;
  }
}
func maxChunksToSorted(arr []int) int {
  h, a, r := map[int]int{}, append([]int{}, arr...), 0
  sort.Ints(a)
  for i, num := range arr {
    add(&h, num, +1)
    add(&h, a[i], -1)
    if len(h) == 0 {
      r++
    }
  }
  return r
}
func add(h *map[int]int, k int, v int) {
  (*h)[k] += v
  if (*h)[k] == 0 {
    delete(*h, k)
  }
}
class Solution {
  public int maxChunksToSorted(int[] arr) {
    Map<Integer, Integer> h = new HashMap<Integer, Integer>();
    int n = arr.length, r = 0;
    int[] a = Arrays.copyOfRange(arr, 0, n);
    Arrays.sort(a);
    for (int i = 0; i < n; i++) {
      add(h, a[i], 1);
      add(h, arr[i], -1);
      if (h.isEmpty()) r++;
    }
    return r;
  }
  private void add(Map<Integer, Integer> h, int k, int v) {
    if (h.containsKey(k)) {
      h.put(k, h.get(k) + v);
      if (h.get(k) == 0) h.remove(k);
    } else h.put(k, v);
  }
}
public class Solution {
  public int MaxChunksToSorted(int[] arr) {
    int n = arr.Length, r = 0;
    int[] a = new int[n];
    Array.Copy(arr, 0, a, 0, n);
    Array.Sort(a);
    Dictionary<int, int> h = new Dictionary<int, int>();
    for(int i = 0; i < n; i++) {
      Add(h, arr[i], 1);
      Add(h, a[i], -1);
      if (h.Count == 0) r++;
    }
    return r;
  }
  private void Add(Dictionary<int, int> h, int k, int v) {
    if (h.ContainsKey(k)) {
      h[k] += v;
      if (h[k] == 0) h.Remove(k);
    } else {
      h.Add(k, v);
    }
  }
}
typedef struct {
    int k;
    int v;
    UT_hash_handle hh;
} HashItem;
static inline int cmp(const void *pa, const void *pb) {
  return *(int*)pa - *(int*)pb;
}
void add(HashItem* *h, int k, int v) {
  HashItem *pEntry = NULL;
  HASH_FIND_INT(*h, &k, pEntry);
  if (pEntry == NULL) {
    pEntry = malloc(sizeof(HashItem));
    pEntry->k = k;
    pEntry->v = 0;
    HASH_ADD_INT(*h, k, pEntry);
  }
  pEntry->v += v;
  if (pEntry->v == 0) {
    HASH_DEL(*h, pEntry);
    free(pEntry);
  }
}
int maxChunksToSorted(int* arr, int arrSize){
  HashItem *h = NULL;
  int* a = malloc(sizeof(int) * arrSize);
  memcpy(a, arr, sizeof(int) * arrSize);
  qsort(a, arrSize, sizeof(int), cmp);
  int r = 0;
  for (int i = 0; i < arrSize; i++) {
    add(&h, a[i], 1);
    add(&h, arr[i], -1);
    if (HASH_COUNT(h) == 0) r++;
  }
  return r;
}
class Solution {
public:
  int maxChunksToSorted(vector<int>& arr) {
    unordered_map<int, int> h;
    int n = arr.size(), r = 0;
    vector<int> a = arr;
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
      add(&h, a[i], 1);
      add(&h, arr[i], -1);
      if (h.size() == 0) r++;
    }
    return r;
  }
  void add(unordered_map<int, int> *h, int k, int v) {
    (*h)[k] += v;
    if ((*h)[k] == 0) (*h).erase(k);
  }
};
class Solution:
  def maxChunksToSorted(self, arr: List[int]) -> int:
    h, r, a = {}, 0, sorted(arr) # 字典
    for i, num in enumerate(arr):
      self.add(h, num, 1)
      self.add(h, a[i], -1)
      if len(h) == 0: r += 1
    return r
  def add(self, h: Dict[int, int], k: int, v: int):
    h[k] = h.get(k, 0) + v
    if h[k] == 0: del h[k]
class Solution:
  def maxChunksToSorted(self, arr: List[int]) -> int:
    h, r, a = Counter(), 0, sorted(arr) # 可计数哈希对象
    for i, num in enumerate(arr):
      self.add(h, num, 1)
      self.add(h, a[i], -1)
      if len(h) == 0: r += 1
    return r
  def add(self, h: Counter, k: int, v: int):
    h[k] += v
    if h[k] == 0: del h[k]

广度优先搜索,深度优先搜索(前序遍历、中序遍历、后序遍历),递归、迭代(单栈、双栈和莫里斯),用减去每行起始序号技巧缩小数据范围,求解《662. 二叉树最大宽度》
广度优先搜索(队列 / 列表 + 层序遍历),深度优先搜索(前序遍历、中序遍历(包含莫里斯)、后序遍历),递归、迭代(单栈),用减去每行起始序号技巧缩小数据范围,求解《662. 二叉树最大宽度》
自定义排序,二分查找(upper_bound / lower_bound + 双指针 / 传递回调函数)2 算法 4 解法,slice / array_slice / subList / Arrays.copyOfRange / GetRange / memcpy 截取列表,求解《658. 找到 K 个最接近的元素》
自定义排序,二分查找(upper_bound / lower_bound + 双指针 / 直接找左边界)2 算法 4 解法,slice / array_slice / subList / Arrays.copyOfRange / GetRange / memcpy 截取列表,传递函数,求解《658. 找到 K 个最接近的元素》
哈希表(用 uthash / Dictionary / dict / HashMap / unordered_map 等 + 定长列表实现),排序 + 拼接字符串 2 算法,求解《1460. 通过翻转子数组使两个数组相等》
哈希表(用 uthash / Dictionary / dict / HashMap / unordered_map 等 + 定长列表实现),排序 + 拼接字符串 2 算法,用 join / implode / fmt.Sprint 将列表转字符串比较,用 Array.equal/ (int[]).SequenceEqual 比较列表,C++ 直接比较 vector<……