LC.P768[最多能完成排序的块II]

方法一：栈+贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxChunksToSorted(int[] arr) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int x : arr) {
            if (!stack.isEmpty() && x < stack.peek()) {
                int max = stack.poll();
                while (!stack.isEmpty() && x < stack.peek()) stack.poll();
                stack.push(max);
            } else {
                stack.push(x);
            }
        }
        return stack.size();
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$