768.md

768. Max Chunks To Make Sorted II

Solution 1 (time O(n), space O(n))

class Solution(object):
    def maxChunksToSorted(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        stack = []
        for num in arr:
            if stack and num < stack[-1]:
                t = stack.pop()
                while stack and num < stack[-1]:
                    stack.pop()
                stack.append(t)
            else:
                stack.append(num)
        return len(stack)