【Day 6 】2024-08-20 - 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]之间。

[akxuan]

观察规律， 尤其是[ 2,1,3,4,4] 这个例子， 我们想filter 掉 1 ， 但是需要 保留两个4. 用单调栈久可以。 monotone stack

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

        for n in arr: 

            while monotone and n < monotone[-1]: 

                n = max(n,monotone.pop())  # 这里是个小坑， 我们想要保留某前一个值或者当前值得最大值
            monotone.append(n)
        print(monotone)
        return len(monotone)

时空复杂度都是 O(N), N = len(arr)

注意的是想清楚到底要做什么， pop 的trigger 是什么。以下是个错误写法， 想去判断， 实际上就是max(n, pop())：

                pre = -1
                while monotone and n < monotone[-1]: 
                    pre = monotone.pop()
                if n<pre: 
                    monotone.append(pre)
                else: 
                    monotone.append(n)

[jialigogogo]

思路

每个分段里的所有值，大于左边分段里的最大值

代码

public static int maxChunksToSorted(int[] arr) {
        LinkedList<Integer> l = new LinkedList<>();
        for (int a : arr) {
            if (l.isEmpty() || a >= l.peek()){
                // 保留每个分段的最大值
                l.push(a);
            } else {
                // 取出当前分段最大值
                int max = l.pop();
                while (!l.isEmpty() && l.peek() > a){
                    // 右边的值小于左边分段最大值，合并分段
                    l.pop();
                }
                l.push(max);
            }
        }
        return l.size();
    }

复杂度

时间复杂度：O(n)

空间复杂度：O(n)

[panfx]

思路

已经分好的块，始终有：右边块的最小值>=左边块的最大值

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

复杂度

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

[CelesteXiong]

Intuition

Assuming that there are k chunks $$c_1, c_2, ... c_k$$. For every two chunks $ci$ and $c(i+1),$ where $i < k$, this rule exists: $max(ci) <= min(c(i+1))$.

Algorithm

Traverse the array, use an increasing stack to store the current $max(c_i)$. When current element is less than the current $max(c_i)$, pop the stack to merge previous chunks until the top of the stack is not larger than the current element, which means we find the chunk that the current element belongs to. Then we push the $max(c_i)$ back for the above rule in the intuition.

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

Complexity

Assuming that n is the length of the input arrar

1. Time: O(n),
2. Space: O(n)

[zjy-debug]

思路

大于等于前序的最大值且小于等于后序的最小值即可

代码

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        k = 1
        for i in range(1, len(arr)):
            maxIndex = max(arr[: i])
            if maxIndex <= arr[i] and maxIndex <= min(arr[i:]):
                k += 1
        return k

复杂度

时间复杂度：O(N²)

空间复杂度：O(1)

[liudi9047]

class Solution { public int maxChunksToSorted(int[] arr) { int n = arr.length, ans = 0; int[] tmp = arr.clone(); Arrays.sort(tmp); Map<Integer, Integer> map1 = new HashMap<>(), map2 = new HashMap<>(); for (int i = 0; i < n; i++) { map1.put(tmp[i], map1.getOrDefault(tmp[i], 0) + 1); map2.put(arr[i], map2.getOrDefault(arr[i], 0) + 1); if (map1.equals(map2)) ans++; } return ans; } }

[peggyhao]

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

time: O(n) space: O(n)

[Fightforcoding]

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        left_max = [0]*len(arr)
        right_min =[float('inf')]*len(arr)
        chunk = 1
        left_max[0] = arr[0]
        for i in range(1, len(arr)):
            left_max[i] = max(left_max[i-1], arr[i])
        right_min[len(arr)-1]=arr[len(arr) -1]
        for i in range(len(arr)-2,-1,-1):
            right_min[i] = min(right_min[i+1], arr[i])
            print(right_min[i])
        for i in range(len(arr)-1):
            if left_max[i]<=right_min[i+1]:
                chunk+=1
        return chunk

Time complexity O(n) Space complexity O(n)