【Day 6 】2021-12-17 - 768. 最多能完成排序的块 II

[azl397985856]

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

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/max-chunks-to-make-sorted-ii/

前置知识

• 栈
• 单调栈
• 队列

  题目描述

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

[yan0327]

思路： 块的关键为升序，因此如果出现降序，则说明要往前遍历寻找比当前值的更小值凑成一个块。 因此本题适合用栈来实现。【栈是单调栈，栈顶-》栈底依次减少】 遍历数组，关键判断栈。 若当前值大于栈顶值，则直接入栈。 若当前值小于栈顶值，则先把栈顶值存在临时变量temp，然后for循环依次遍历栈顶， 如果栈顶元素大于x则继续遍历，否则就退出for循环。将temp临时变量入栈 【用temp保存此前的最大值，是为了保证后来进来的变量如果小的话，则属于前一个块】 最后输出栈的长度，可以得到所分的块数。

func maxChunksToSorted(arr []int) int {
    stack := []int{}
    for _,x := range arr{
        if len(stack)>0 && x < stack[len(stack)-1]{
            temp := stack[len(stack)-1]
            for len(stack)>0 && x < stack[len(stack)-1]{
            stack = stack[:len(stack)-1]
            }
            stack = append(stack,temp)
        }else{
            stack = append(stack,x)
        }
    }
    return len(stack)
}

时间复杂度：O（N） 空间复杂度：O（N）

[Alfie100]

【Python双解】

LeetCode题目连接：https://leetcode-cn.com/problems/max-chunks-to-make-sorted-ii/

1. 单调栈

可采用单调栈（单调不减），其中单调栈中的每一个元素代表每一块中的最大值。

Python代码

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:

        stack = [arr[0]]
        for num in arr[1:]:

            if num >= stack[-1]:    # 大于栈顶【栈中的最大值】
                stack.append(num)
            else:                   # 小于栈顶
                cur_ma = stack.pop()    # 记录下栈顶
                while stack and num < stack[-1]:    # 移除栈中大于当前值num的所有元素
                    stack.pop()
                stack.append(cur_ma)    # 栈顶复位

        return len(stack)

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为数组 $arr$ 的长度。
• 空间复杂度：$O(n)$。

2. 排序 + 前缀和

arr元素存在重复，简单的排序计数不可行。 为排除重复元素的干扰，可采用前缀和 等方法排除重复项的干扰。

Python代码

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:

        prex, prey = 0, 0
        ans = 0
        for (x, y) in zip( arr, sorted(arr) ):  # '未排序' 与 '排序后' 的比较
            prex += x
            prey += y
            if prex == prey:    # 前缀和与排序后的相等，独立成块数目+1
                ans += 1

        return ans

复杂度分析

• 时间复杂度：$O(n \log n)$，涉及到排序，其中 $n$ 为数组 $arr$ 的长度。
• 空间复杂度：$O(n)$。

[zjsuper]

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        lists = []
        temp = []
        for i in range(len(arr)-1):
            temp.append(arr[i])
            if max(temp) <= min(arr[i+1:]):
                lists.append(temp)
                temp = []
            else:
                pass
        if len(lists) == 0:
            return 1
        else:
            return len(lists)+1

[wxj783428795]

思路

1. 分块的标准是：前面的块的最大值，要小于后面块的最小值。这样才能保证块分别排序再链接后，是整体升序的。
2. 因此，循环遍历整个数组，当数组为空或者栈顶值大于当前元素，说明当前元素应该和前面的块分到一起。

代码

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function (arr) {
    let stack = [];
    for (let i = 0; i < arr.length; i++) {
        if (stack.length !== 0 && stack[stack.length - 1] > arr[i]) {
            let temp = stack.pop();
            while (stack.length !== 0 && stack[stack.length - 1] > arr[i]) {
                stack.pop()
            }
            stack.push(temp);
        } else {
            stack.push(arr[i])
        }
    }
    return stack.length
};

复杂度分析

复杂度分析不是很会，不一定对，如果有错，请指正。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[MongoCZK]

思路

• 使用滑动窗口同时扫描原数组和排序数组，当窗口中数字的和一样时，就将窗口内的元素分块

  代码

  var maxChunksToSorted = function (arr) {
  const sorted = [...arr];
  sorted.sort((a, b) => a - b);
  
  let count = 0,
  sum1 = 0,
  sum2 = 0;
  
  for (let i = 0; i < arr.length; i++) {
  sum1 += arr[i];
  sum2 += sorted[i];
  sum1 ===  sum2 && count++;
  }
  
  return count;
  };

  复杂度分析

• 时间复杂度：O(NlogN)，N 为数组长度，数组排序时间认为是NlogN，滑动窗口遍历数组时间为N
• 空间复杂度: O(N)，N 为数组长度

[zwx0641]

class Solution {
    public int maxChunksToSorted(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (!stack.isEmpty() && stack.peek() > arr[i]) {
                int tmp = stack.pop();
                while (!stack.isEmpty() && stack.peek() > arr[i]) {
                    stack.pop();
                }
                stack.push(tmp);
            } else {
                stack.push(arr[i]);
            }
        }
        return stack.size();
    }
}

[Grendelta]

思路

将arr排序，之后对比arr和排序后的arr的前n项和有多少个相等，就可以分多少组

代码

class Solution(object): def maxChunksToSorted(self, arr): """ :type arr: List[int] :rtype: int """ maximum, res = 0, 1 for i in range(len(arr)): maximum = max(arr[i], maximum) if i == len(arr) - 1: break elif min(arr[i+1:]) >= maximum: res += 1 return res

复杂度

时间复杂度 O(NlogN}

空间复杂度 O(N)

[wangzehan123]

代码

• 语言支持：Java

Java Code:

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int n = arr.length;
        int[] forward = new int[n];
        int[] backward = new int[n];

        forward[0] = arr[0];
        for (int i = 1; i < n; i++) {
            forward[i] = Math.max(forward[i-1], arr[i]);
        }

        backward[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            backward[i] = Math.min(backward[i + 1], arr[i]);
        }

        int res = 0;
        for (int i = 0; i < n - 1; i++) {
            if (forward[i] <= backward[i + 1]) res++;
        }

        return res + 1;
    }
}

[ginnydyy]

Problem

https://leetcode.com/problems/max-chunks-to-make-sorted-ii/

Note

• mono stack
• non-increasing subarray cannot be divided
• non-decreasing subarray can be divided

Solution

class Solution {
    public int maxChunksToSorted(int[] arr) {
        if(arr == null || arr.length == 0){
            return 0;
        }

        Stack<Integer> monoStack = new Stack<>(); // mono increasing stack
        for(int num: arr){
            if(monoStack.isEmpty() || num >= monoStack.peek()){
                monoStack.push(num);
                continue;
            }

            int top = monoStack.pop();
            while(!monoStack.isEmpty() && num < monoStack.peek()){
                monoStack.pop();
            }
            monoStack.push(top);
        }

        return monoStack.size();
    }
}

Complexity

• T: O(n) n is the length of arr
• S: O(n) for the stack

[CodeWithIris]

Note

• Use a stack to record the number.
• When the stack is not empty and the number is smaller than the top of the stack, pop the numbers in the stack until the top of the stack is bigger then the number.
• When the number is bigger than the top of the stack, just push the number into the stack.
• Return the size of the stack.

Solution (C++)

 class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int maxx = arr[0];
        stack<int> stk;
        stk.push(arr[0]);
        for(int i = 1; i < arr.size(); ++i){
            if(arr[i] >= maxx){
                maxx = arr[i];
                stk.push(arr[i]);
            }else{
                while(!stk.empty() && stk.top() > arr[i]){
                    stk.pop();
                }
                stk.push(maxx);
            }
        }
        return stk.size();
    }
};

Complexity

• T: O(n)
• S: O(n)

[Yutong-Dai]

思路

单调栈

代码

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        monotoneStack = [arr[0]]
        for i in range(1,len(arr)):
            element = arr[i]
            if element >= monotoneStack[-1]:
                monotoneStack.append(element)
            else:
                topMax = monotoneStack[-1]
                while monotoneStack and element < monotoneStack[-1]:
                    monotoneStack.pop(-1)
                monotoneStack.append(topMax)
        return len(monotoneStack)

复杂度

• 时间: O(n)
• 空间: O(n)

[feifan-bai]

思路

1. Monotonic stack
2. Non-increasing subarray cannot be divided(stack[-1] > num)
3. Non-decreasing subarray can be divided(stack[-1]<= num, stack.append(num)) 代码

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

   复杂度分析

   • 时间复杂度：O(N)
   • 空间复杂度：O(N)

[laofuWF]

# monotonic stack (ascending)
class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        stack = []

        for n in arr:
            curr_max = n
            while stack and stack[-1] > n:
                curr_max = max(curr_max, stack.pop())
            stack.append(curr_max)

        return len(stack)

[LannyX]

思路

use monotonic stack

代码

class Solution {
    public int maxChunksToSorted(int[] arr) {
        Stack<Integer> stack = new Stack<>();

        for(int num : arr){
            if(!stack.isEmpty() && num < stack.peek()){
                int top = stack.pop();
                // use while because num needs to compare every element in stack
                while(!stack.isEmpty() && num < stack.peek()){
                stack.pop();
                }
                stack.push(top);
            }else{
                stack.push(num);
            }

        }
        return stack.size();
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(N)

[Alexno1no2]

使用单调栈，每个元素代表每个块中的最大值

复杂度分析

时间复杂度：O(N)，其中 N 为数组长度。 空间复杂度：O(N)

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        stack = []
        for num in arr:
            # 递增栈
            if not stack or stack[-1] <= num:
                stack.append(num)
            else:
                cur_max = stack.pop()
                while stack and stack[-1] > num:
                    stack.pop()
                stack.append(cur_max)
        return len(stack)

[ZacheryCao]

Idea

Monotonic Stack. The stack will store the largest element of each chunk.

Code

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        stack = []
        for i in arr:
            largest = i
            while stack and stack[-1] > i:
                largest = max(largest, stack.pop())
            stack.append(largest)
        return len(stack)

Complexity:

Space: O(N) Time: O(N)

[Bingbinxu]

思路 采用官方思路：利用单调栈存储 遇到一个数小于栈的最大值，只保留最大值，否则就相当于增加一个块 弹出递增的，以前的递增会因为一个低值而必须把这个低值包含进去 代码

class Solution {
public:
     int maxChunksToSorted(vector<int>& arr) {
        stack<int> stack;
        for(int i =0;i<arr.size();i++){
            if(!stack.empty()&&stack.top()>arr[i]){
                //遇到一个数小于栈的最大值，只保留最大值，否则就相当于增加一个块
                int max = stack.top();
                //弹出递增的，只保留最大值
                while(!stack.empty()&&stack.top()>arr[i]){
                    stack.pop();
                }
                stack.push(max);
            }else{
                stack.push(arr[i]);
            }
        }
        return stack.size();
    }
};

复杂度 时间复杂度：遍历O（N） 空间复杂度：栈存储，最大O（N）

[XinnXuu]

思路

栈内保存每个块的最大值。对于nums中的每个i，如果不小于当前栈顶则入栈。否则先保存现在的栈顶，再将之前比该元素大的栈内元素全部出栈（也就是将这些元素以及i全部融合入以这个栈顶值为最大值的块）。

代码

class Solution {
    public int maxChunksToSorted(int[] nums) {
        Stack<Integer> stack = new Stack<Integer>();
        for (int i : nums){
            if (!stack.empty() && i < stack.peek()){
                int cur = stack.pop();
                while (!stack.empty() && i < stack.peek()){
                    stack.pop();
                }
                stack.push(cur);

            } else {
                stack.push(i);
            }
        }
        return stack.size();
    }
}

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[BpointA]

思路

max+max_count构成组合进行比较

代码

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int [] new_arr=new int[arr.length];
        int m0=-1,m0_count=0,m1=-1,m1_count=0;
        System.arraycopy(arr,0,new_arr,0,arr.length);
        Arrays.sort(new_arr);
        int cnt=0;
        for (int i=0;i<arr.length;i++)
        {
            if (new_arr[i]!=m0)
            {
                m0=new_arr[i];
                m0_count=1;
            }
            else
            {
                m0_count+=1;
            }
            if (arr[i]==m1)
            {
                m1_count+=1;
            }
            else if (arr[i]>m1)
            {
                m1=arr[i];
                m1_count=1;            
            }
         if (m0==m1 && m0_count==m1_count)
         {cnt+=1;}
        
        

        }
        return cnt;

    }
}

[CoreJa]

思路

先取arr[0]作为一个max_num，从右往左扫，找到第一个比max_num要小的元素small，这里表示从0开始到small这个区间可能是第一个"块"(因为它俩顺序反了，必须当成一个块)

接着在这个可能的"块"里找一个最大值作为max_num，继续从右往左扫，重复上面的操作，直到这个块的长度不再增加(或者是max_num不变)，说明这个块确定下来了，cnt+=1.

重复这个步骤，直到整个list扫完

另一个思路是题解给的单调栈，比我这个好多了。

代码

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        n = len(arr)
        i, j = 1, n - 1
        max_stack = [arr[0]]
        while i < n:
            while i < j and max_stack[-1] <= arr[j]:
                j -= 1
            if max_stack[-1] <= (t := max(arr[i:j + 1])):
                if i == j:
                    max_stack.append(t)
                else:
                    max_stack[-1] = t
            i, j = j + 1, n - 1

        return len(max_stack)

    def maxChunksToSorted2(self, arr: List[int]) -> int:
        stack = []
        for i in arr:
            largest = i
            while stack and stack[-1] > i:
                largest = max(largest, stack.pop())
            stack.append(largest)
        return len(stack)

[moirobinzhang]

    Stack<int> monoStack = new Stack<int>();

    for (int i = 0; i < arr.Length; i++)
    {
        if (monoStack.Count() > 0 && monoStack.Peek() > arr[i])
        {
            int currentVal = monoStack.Pop();

            while (monoStack.Count() > 0 && monoStack.Peek() > arr[i] )
                monoStack.Pop();

            monoStack.Push(currentVal);
        }
        else 
        {
            monoStack.Push(arr[i]);
        }

    }

    return monoStack.Count(); 

[shamworld]

var maxChunksToSorted = function(arr) {
    let sortArr = [...arr];
    sortArr.sort((a,b)=>a-b);
    let count = 0,num1 = 0,num2 = 0;
    for(let i = 0; i < arr.length; i++){
        num1 += arr[i];
        num2 += sortArr[i];
        if(num1==num2){
            count++;
        }
    }
    return count;
};

[callmeerika]

思路

条件：前面的块的最大值要小于后面的块的最小值 先取数组第一个元素为第一个块，与后面的大块比较，满足条件则抛出，不满足则将第二个元素塞进第一个块，继续比较，直到数组所有的元素都被抛出，循环结束

代码

var maxChunksToSorted = function(arr) {
    let n = 0;
    while(arr.length > 0) {
        let pre = [arr.shift()];
        while(Math.max(...pre) > Math.min(...arr)){
            pre.push(arr.shift());
        }
        n = n + 1;
    }
    return n;
};

复杂度

时间复杂度：O(n^2)

[ZJP1483469269]

思路

借助栈存储子序列的最大值，最后输出即为栈长度

代码

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        stack = []
        for x in arr:
            if not stack or stack[-1] <= x:
                stack.append(x)
            elif stack[-1] > x:
                tmp = stack[-1]
                while stack and stack[-1] > x:
                    stack.pop()
                stack.append(tmp)
        return len(stack)

复杂度分析

时间复杂度：O（n） 空间复杂度：O（n）

[KennethAlgol]

语言

java

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

[LAGRANGIST]

class Solution { public: int maxChunksToSorted(vector& arr) { stack stk; for(int i =0;i<arr.size();i++){ if(!stk.empty()&&stk.top()>arr[i]){

            int cur = stk.top();
            // 维持栈的单调递增
            while(!stk.empty()&&stk.top()>arr[i]){
                stk.pop();
            }
            stk.push(cur);
        }else{
            stk.push(arr[i]);
        }
    }
    // 栈存的是块信息，因此栈的大小就是块的数量
    return stk.size();
}

};

[SeventeenCui]

思路

哈希表 + 贪心 代码

class Solution {
public:
    int maxChunksToSorted(vector<int>& a) {
        auto b = a;
        sort(b.begin(), b.end());
        unordered_map<int, int> cnt;
        int res = 0;
        for (int i = 0, s = 0; i < a.size(); i ++ ) {
            if (cnt[a[i]] == 1) s -- ;
            else if (cnt[a[i]] == 0) s ++ ;
            cnt[a[i]] -- ;
            if (cnt[b[i]] == -1) s -- ;
            else if (cnt[b[i]] == 0) s ++ ;
            cnt[b[i]] ++ ;
            if (!s) res ++ ;
        }
        return res;
    }
};

复杂度分析

时间复杂度 O(nlgn) 空间复杂度 O(n)

[Aobasyp]

思路： 用一个单调递增的栈，返回栈的元素个数即可

class Solution { public: int maxChunksToSorted(vector& arr) { stack stack; for(int i =0;i<arr.size();i++){ // 遇到一个比栈顶小的元素，而前面的块不应该有比 a 小的 // 而栈中每一个元素都是一个块，并且栈的存的是块的最大值，因此栈中比 a 小的值都需要 pop 出来 if(!stack.empty()&&stack.top()>arr[i]){ // 我们需要将融合后的区块的最大值重新放回栈 // 而 stack 是递增的，因此 stack[-1] 是最大的 int cur = stack.top(); // 维持栈的单调递增 while(!stack.empty()&&stack.top()>arr[i]){ stack.pop(); } stack.push(cur); }else{ stack.push(arr[i]); } } // 栈存的是块信息，因此栈的大小就是块的数量 return stack.size(); } };

时间：O(N) 空间：O(N)，

[zwmanman]

思路

1.use a dict to store each occurrence of a number

2. count the different of occurrence 3.when there is no diff ans + 1

代码

class Solution(object):
    def maxChunksToSorted(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        dict1 = collections.defaultdict(int)
        non_zero_count = 0
        ans = 0
        for a, b in zip(arr, sorted(arr)):
            if dict1[a] == 0:
                non_zero_count += 1
            if dict1[a] == -1:
                non_zero_count -= 1
            dict1[a] += 1 

            if dict1[b] == 0:
                non_zero_count += 1
            if dict1[b] == 1:
                non_zero_count -= 1
            dict1[b] -= 1

            if non_zero_count == 0:
                ans += 1

        return ans

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(N)

[Flower-F]

解题思路

将栈中每一个减序列压缩合并成该序列的最大的值，最终返回栈的长度。

代码

function maxChunksToSorted(arr: number[]): number {
    const stack: number[] = [];
    for (const num of arr) {
        if (stack.length && num < stack[stack.length - 1]) {
            const top = stack[stack.length - 1];
            while (stack.length && num < stack[stack.length - 1]) {
                stack.pop();
            }
            stack.push(top);
        } else {
            stack.push(num);
        }
    }
    return stack.length;
};

复杂度

时间：O(n) 空间：O(n)

[ray-hr]

思路

贪心算法。建立一个栈，存储每个块的最大值，栈的长度即为划分块的个数。 栈内元素通过比较栈顶head和数组内num进行更新：如果num>=head,将num元素push入栈，如果num<head则pop出head并存储，接着继续比较栈顶元素，直到num>=head,将之前贮存的head重新入栈。

代码

class Solution:
    def maxChunksToSorted(self, arr: [int]) -> int:
        stack = []
        for num in arr:
            if stack and num < stack[-1]: 
                head = stack.pop()
                while stack and num < stack[-1]: stack.pop()
                stack.append(head)
            else: stack.append(num)
        return len(stack)

[xianxianxianyu]

并查集

class Solution {
public:
    int end=0;
    bool check(vector<int>&temp,vector<int>&store){
        sort(store.begin(),store.end());
        for(int i=store.size()-1;i>=0;i--){
            if(store[i]!=temp[i]){
                return false;
            }
        }
        end=store.size()>=temp.size()?-1:temp[store.size()];
        return true;
    }
    int maxChunksToSorted(vector<int>& arr) {
        vector<int>temp=arr;
        vector<int>store;
        int res=0;
        bool flag1=false;
        end=temp[0];
        sort(temp.begin(),temp.end());
        for(int i=0;i<arr.size();i++){
            if(i+1==arr.size()){
                res++;
                break;
            }
            store.push_back(arr[i]);
            if(arr[i]==end){
                flag1=true;
            }
            if(flag1&&check(temp,store)){
                flag1=false;
                res++;
            }
        }
        return res;
    }
};

[HondryTravis]

思路

贪心

代码

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function (arr) {
  const stack = []
  const peek = array => array.length >= 1 ? array[array.length - 1] : 0

  for (const n of arr) {
    const max = peek(stack)

    if (stack.length && n < max) {
      // 循环出栈 
      while (stack.length && n < peek(stack)) stack.pop()

      // 更新 max
      stack.push(max)      
    } else stack.push(n)
  }
  // 返回高度
  return stack.length
};

复杂度分析

时间复杂度 O(n)

空间复杂度 O(n)

[potatoMa]

思路1：滑动窗口

---

原数组与排好序后的数组比较，当窗口内的数字和相等则可以分为一个块。

代码

---

JavaScript Code

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function(arr) {
    const sortedArr = [...arr].sort((a, b) => a - b);
    let sum1 = 0, sum2 = 0, res = 0;
    for (let i = 0;i < sortedArr.length;i++) {
        sum1 += sortedArr[i];
        sum2 += arr[i];
        if (sum1 === sum2) {
            res++;
        }
    }
    return res;
};

复杂度分析

---

时间复杂度：O(NlogN + N) = O(NlogN)

空间复杂度：O(N)

思路2：单调栈

---

通过遍历数组间接找出每个块中的最大值，当遇到更大的值时则可以将其置为新的块，推入栈顶；遇到较小的值时，则降栈顶依次弹出找到小于等于该值的项，并进行合并。

代码

---

JavaScript Code

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function(arr) {
    const stack = [];
    for (let i = 0;i < arr.length;i++) {
        if (!stack.length || stack[stack.length - 1] <= arr[i]) {
            stack.push(arr[i]);
        } else if (stack[stack.length - 1] === arr[i]) {
            continue;
        } else if (stack[stack.length - 1] > arr[i] && stack.length !== 1) {
            let top = stack.pop();
            while (stack[stack.length - 1] > arr[i]) {
                stack.pop();
            }
            stack.push(top);
        }
    }
    return stack.length;
};

复杂度分析

---

时间复杂度：O(N)

空间复杂度：O(N)

[falconruo]

思路: 利用单调队列(monotonic queue/stack)或单调栈来存放每个有效分块(Chunk)的最大值，遍历整个数组arr，比较当前数组元素与栈里元素的大小

复杂度分析:

1. 时间复杂度: O(n), n为给定数组的元素个数
2. 空间复杂度: O(n), n为给定数组的元素个数

代码(C++):

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> s;

        for (int i = 0;i < arr.size();i++) {
            if (s.empty() || s.top() <= arr[i])
                s.push(arr[i]);
            else {
                int max_val = s.top();

                while (!s.empty() && s.top() > arr[i]) // here is a while the worst case is O(n) here, but overall worst case is O(k * n), average is O(n)
                    s.pop();
                s.push(max_val);
            }
        }

        return s.size();
    }
};

[rootdavid]

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
      stack<int> maxStk;

      maxStk.push(arr[0]);

      for (int i = 1; i < arr.size(); i++) {
        if (arr[i] < maxStk.top()) {
          int maxNum = maxStk.top();
          while (!maxStk.empty() && arr[i] < maxStk.top()) maxStk.pop();
          maxStk.push(maxNum);
        } else {
          maxStk.push(arr[i]);
        }
      }

      return maxStk.size();

    }
};

[2024-ZWR]

class Solution(object):
    def maxChunksToSorted(self, arr):
        count = collections.defaultdict(int)
        ans = nonzero = 0

        for x, y in zip(arr, sorted(arr))
            count[x] += 1
            if count[x] == 0: nonzero -= 1
            if count[x] == 1: nonzero += 1

            count[y] -= 1
            if count[y] == -1: nonzero += 1
            if count[y] == 0: nonzero -= 1

            if nonzero == 0: ans += 1

        return ans

时间复杂度: O(N log N)O(NlogN)，其中 N 为 arr 的长度。空间复杂度: O(N)。

[jiaqiliu37]

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        stack = []
        for num in arr:
            if stack and stack[-1] > num:
                curr_block_max = stack.pop()
                while stack and stack[-1] > num:
                    stack.pop()
                stack.append(curr_block_max)
            else:
                stack.append(num)

        return len(stack)

        '''
        ans = sum1 = sum2 = 0
        for a,b in zip(arr, sorted(arr)):
            sum1 += a
            sum2 += b
            ans += (sum1 == sum2)
        return ans
        '''

        '''
        ans = 0
        arr_sorted = sorted(arr)
        for k in range(len(arr)):
            ans += (sorted(arr[:k]) == arr_sorted[:k])

        return ans
        '''

        '''
        count_1 = defaultdict(int)
        count_2 = defaultdict(int)
        ans = 0
        for a,b in zip(arr, sorted(arr)):
            count_1[a] += 1
            count_2[b] += 1
            ans += count_1 == count_2

        return ans
        '''

[charlestang]

思路

切割后，排序，再合并，和原来的数组排序后一致，说明每一块的最大值，和排序后的对应值，位置相同。

每一块的最大值是块切割的边界。可以用一个栈记住每一块的最大值。

同时要保证，这一块里的最小值要 不小于 上一块的最大值。

代码

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

复杂度分析

时间复杂度：O(n) 每个元素最多进栈一次，出栈一次

空间复杂度：O(n)

[RocJeMaintiendrai]

代码

class Solution {
    public int maxChunksToSorted(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < arr.length; i++) {
            int num = arr[i];
            int tmp = -1;
            while(!stack.isEmpty() && stack.peek() > num) {
                tmp = Math.max(stack.pop(), tmp);
            }
            if(tmp == -1) {
                stack.push(num);
            } else {
                stack.push(tmp);
            }
        }
        return stack.size();
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[de0002ou]

思路

代码

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        ans = 0
        cur_max = 0
        for i in range(len(arr)):
            if arr[i] > cur_max:
                cur_max = arr[i]
            if cur_max == i:
                ans += 1
        return ans

复杂度分析 时间复杂度：O(n) 空间复杂度：O(n)

[Leonalhq]

思路： 大概使用stack是想到的， 具体的先局部再整体容我琢磨琢磨

defmaxChunksToSorted(self, arr: List[int]) ->int:
        if not arr 
          return0;

    st = [];
    st.append(arr[0]);
    for(inti=1;i<len(arr)i++){

        if(arr[i]>=st[-1]){
            st.append(arr[i]);
            continue;
        }
        inttemp = st[-1];
        while(st && arr[i] < st[-1]_
            st.pop();

        st.append(temp); 
    }
    return len(st)

[cszys888]

class Solution(object):
    def maxChunksToSorted(self, arr):
        count = collections.defaultdict(int)
        non_zero_cnt = 0
        ans = 0

        for a, b in zip(arr, sorted(arr)):
            if count[a] == -1: non_zero_cnt -= 1
            if count[a] == 0: non_zero_cnt += 1
            count[a] += 1
            if count[b] == 1: non_zero_cnt -= 1
            if count[b] == 0: non_zero_cnt += 1
            count[b] -= 1
            if non_zero_cnt == 0: ans += 1

        return ans

Time complexity: O(NlogN) Space complexity: O(N)

[Yachen-Guo]

解题思路：采用栈作为基础数据结构，并通过arr的遍历来维护栈的单调性。

observation1: 对于单调数组，可以拆分的最多完成排序的块=数组size => return stack.size();

observation2: 入栈条件，大于数组的最大值 => 在每次pop数组、维护单调栈的过程中保留最大值，并在完成维护后入栈， stack.push(max)。

时间复杂度：O(N)

class Solution {
    public int maxChunksToSorted(int[] arr) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(arr[0]);
        for(int i = 1; i < arr.length; i++){
            int tmp = stack.peek();
            if(arr[i] >= tmp){
                stack.push(arr[i]);
            } else{
                while(arr[i] < stack.peek()){
                    stack.pop();
                    if(stack.isEmpty()){
                        break;
                    }
                }
                stack.push(tmp);
            }
        }
        return stack.size();
    }
}

[z1ggy-o]

思路

chunk 划分的核心在于，后一个 chunk 中最小的元素要大于等于前一个 chunk 中最大的元素。 这个要求等效于，在遍历 arr 的过程中，每次遇到升序的情况，我们都可以划分一个新的 chunk。

上面的核心基础思想之下，我们来考虑 arr 的情况，一共有 4 种：

• 一直升序
• 一直降序
• 先降后升
• 先升后降

核心基础思想下，简单的通过记录一个当前遇到过的最大值即可完成对除了”先升后降“情况的处理。 只记录一个当前最大值无法应对”先升后降“的情况（例，[1,2,3,1,2,3]）因为后面遇到的较小值可能比之前某一个中间 chunk 的最大值还要小。因为我们只记录了最新 chunk 的最大值，就只能将新元素合并至此，但这会使排序失败。

所以，基于核心基础之上，我们需要记录每一个 chunk 的最大值，这样才可以将新的元素进行正确的合并。 继而，问题的最后就转变成了，如何记录每个 chunk 的最大值。这里的选择我觉得是很多的，例如：

• queue：可以方便的把之前错误划分的 chunk 去掉。
• vector (dynamic array）：每个 chunk 的最大值存放在相应的 index
• stack：每个 chunk 的最大值 push 进去即可

此问题中，使用上面三个 container 的复杂度是相同的，都是从后往前一次确认各个 chunk 的最大值。 因为 stack 的代码最简单，我选择用 stack 来进行实现。

代码

CPP

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> s;
        int max;

        s.push(arr[0]);
        for (int i = 1; i < arr.size(); i++) {
            if (arr[i] >= s.top()) {
                s.push(arr[i]);
            } else {
                max = s.top();  // keep the greatest element until now
                s.pop();

                while (!s.empty() && arr[i] < s.top()) {
                    s.pop();
                }
                s.push(max);
            }
        }

        return s.size();
    }
};

复杂度分析

• 时间：O(N). N is the size of the array.
• 空间：O(M). M is # of the chunks

[gentleman-goodman]

Day6_768_最多能完成排序的块2_lc题解

思路

*实在是不会，栈stack不懂，看lc题解的，顺带添加了注释在代码上，引用lc题解的思路，
 * https://leetcode-cn.com/problems/max-chunks-to-make-sorted-ii/solution/768-zui-duo-neng-wan-cheng-pai-xu-de-kua-u059/
 * 可以明确的是每个分块都有一个最大值head，且这些head从左到右递增，
 * 因此只要知道head的数量就知道块的数量，用栈来存储这些head
 * <p>
 * 遍历数组
 * i. 如果当前的数比前一个块的最大值小，也就是比栈顶元素小，并入前一个块
 * 要注意的是如果当前数比倒数第二个块的最大值也要小，前两个块也需要合并，因此这里需要用一个循环
 * ii. 如果当前的数比前一个块的最大值要大，这个数形成一个新的块，把当前的数加入stack中
 * iii. 如果栈为空，当前数直接入栈
 * （情况ii和iii可以合并）
 * <p>
 * 返回栈的长度
 *
 *
 * 首先栈里面总是存的是每一个块里面最大的数  ，最大的数由head保存，while则是用来比较如果当前数比倒数第二个块的最大值也要小，
 * 前两个块也需要合并，因此这里需要用一个循环
 * 因为之前已经stack.pop取出了一个出去，然后while还要继续去stack.peek比较num，也就是比较倒数第二个块的最大值，如果num还要大，说明就要合并在一起
 * 即去掉倒数第二个，由倒数第一个来顶替
 * 例如2，1，3，0，4，4
 * 最后stack是3，4，4
 * 其中2在里面，num==3的时候，stack为2，3
 * 接着num==0，这个时候0《3，
 * head=3，stack为2
 * 0《2
 * 弹出2，即执行stack.pop();//取出
 * 存回3，head
 */

代码

class Solution {
        public int maxChunksToSorted(int[] arr) {
            Stack<Integer> stack = new Stack<>();
            //for循环arr数组找每个数num
            for (int num : arr) {
                //如果栈中不是空的，并且取出的数是要小于栈中的栈顶，也就是外面的要小于栈内的，外面的要小，
                //如果当前的数比前一个块的最大值小，也就是比栈顶元素小，并入前一个块
                if (!stack.empty() && num < stack.peek()) {
                    //可以明确的是每个分块都有一个最大值head，且这些head从左到右递增，
                    //因此只要知道head的数量就知道块的数量，用栈来存储这些head
                    int head = stack.pop();//取出栈顶的，赋予给head，最大值head，栈内最大的head
                    //要注意的是如果当前数比倒数第二个块的最大值也要小，前两个块也需要合并，因此这里需要用一个循环
                    while (!stack.empty() && num < stack.peek()) {
                        stack.pop();//取出
                    }
                    stack.push(head);
                }//如果外面的数是等于或者大于栈内的，//说明这个数形成一个新的块，把当前的数加入stack中
                //或者是第一个数，也存入栈中
                /* * ii. 如果当前的数比前一个块的最大值要大，这个数形成一个新的块，把当前的数加入stack中
                 * iii. 如果栈为空，当前数直接入栈*/
                else {
                    stack.push(num);
                }
            }
            return stack.size();
        }
    }

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[spacker-343]

思路

和一个已经排序好的数组，同时计数并存进map中，如果两个map键值对一样，说明可以进行分组排序，此时res+1

代码

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int[] sortarr=Arrays.copyOf(arr, arr.length);
        Arrays.sort(sortarr);
        Map<Integer, Integer> countA=new HashMap<>();
        Map<Integer, Integer> countB=new HashMap<>();
        int res=0;
        for(int i=0; i<arr.length; i++){
            countA.put(arr[i], countA.getOrDefault(arr[i], 0)+1);
            countB.put(sortarr[i], countB.getOrDefault(sortarr[i], 0)+1);
            if(countA.equals(countB)){
                res++;
            }
        }
        return res;
    }
}

复杂度

时间复杂度：O(n^2)，排序为O（nlogn）,for遍历一遍数组是O（n），最坏情况每个键值对都要进行匹配，因此是1+2+3+...n=n/2+n^2/2即O(n^2) 空间复杂度：O（n）

[Bochengwan]

思路

从array的尾部开始计算，save当前的最小值，每次前面存在比当前最小值更小的element，则需要从新sort一次。

代码

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        if not arr:
            return 0
        head = [0]*len(arr)
        head[0] = arr[0]

        result = 0
        for i in range(1,len(arr)): 
            head[i] = max(arr[i],head[i-1])
        print(head)
        tail = float('inf')
        for i in range(len(arr)-1,-1,-1):

            if tail>=head[i]:
                result+=1
            tail = min(tail,arr[i])
        return result

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[Husky-Gong]

Note

Use 2 array to record the maximum/minimum value from left and right accordingly

Code

class Solution {
    public int maxChunksToSorted(int[] arr) {
        // use 2 array to record the maximum/minimum value from left and right accordingly
        int[] leftMax = new int[arr.length];
        int[] rightMin = new int[arr.length];

        int tempMax = Integer.MIN_VALUE;
        int tempMin = Integer.MAX_VALUE;

        for (int i = 0; i < arr.length; i++) {
            tempMax = Math.max(arr[i], tempMax);
            leftMax[i] = tempMax;
        }

        for (int i = arr.length-1; i >= 0; i--) {
            tempMin = Math.min(arr[i], tempMin);
            rightMin[i] = tempMin;
        }

        int result = 1;

        for (int i = 0; i < arr.length - 1; i++) {
            if (leftMax[i] > rightMin[i+1]) {
                continue;
            } else {
                result++;
            }
        }

        return result;
    }
}

Complexity

Time Complexity: O(n) Space Complexity: O(n)

[zol013]

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        '''
        #1
        chunks = 0
        for i in range(1, len(arr)+1):
            if sorted(arr[:i]) == sorted(arr)[:i]:
                chunks += 1
        return chunks
        '''
        ''''
        #2
        count_a = defaultdict(int)
        count_b = defaultdict(int)
        ans = 0

        for a, b in zip(arr, sorted(arr)):
            count_a[a] += 1
            count_b[b] += 1
            if count_a == count_b: ans += 1
        return ans
        '''

        '''
        #3
        count = defaultdict(int)
        diff_cnt = 0
        ans = 0
        for a, b in zip(arr, sorted(arr)):
            if count[a] == 0: diff_cnt += 1   ## a's count as positive and b's count as negative, 
            if count[a] == -1: diff_cnt -= 1  ## subarray would match by sort if the current diff count is 0
            count[a] += 1
            if count[b] == 0: diff_cnt += 1
            if count[b] == 1: diff_cnt -= 1
            count[b] -= 1
            if diff_cnt == 0: ans += 1
        return ans
        '''

        stack = []
        for num in arr:
            if stack and stack[-1] > num:
                curr_max = stack[-1]
                while stack and stack[-1] > num:
                    stack.pop()
                stack.append(curr_max)
            else:
                stack.append(num)
        return len(stack)