Python3 - stack O(n) 8 lines 56ms 100%
Keep a non-decreasing stack, whenever a number is non-decreasing, add it to the stack. Note that the stack is actually keep the maximum value of each partition.
Keep a non-decreasing stack, whenever a number is non-decreasing, add it to the stack. Note that the stack is actually keep the maximum value of each partition. \n\nWhenever there is a decreasing number, check if it is possible to merge with the immediate previous partition, i.e. stack[-1]; if it is even smaller than 2 groups before, we need to pop the stack and update the maximum value of that partition. \n\nFor example, let\'s go through the example 5,3,2,4,5,1\n* add 5 to stack, stack = [5]\n* 3 < 5, so ignore it since it can be merged with the previous partition, and stack = [5]; note it means that parition has maximum value 5 still.\n* 2 < 5 same as the previous iteration. stack = [5].\n* 4 < 5 same as before. stack = [5]\n* 6 >= 5, add to stack. stack = [5,6]. This means we can have up tp 2 paritions at this point.\n* stack has more than 2 elements, and 1 < stack[-2] = 5, this means we cannot simply merge 1 into the partition [6], so we need to pop 6; this also means we will merge this partition with partition [5]. After merging, the new parition will have maximum value 6. So finally stack = [6], indicating we have 1 parition with maximum value of 6. \n\nTime complexity O(n).\n\n```python\nclass Solution:\n    def maxChunksToSorted(self, arr: List[int]) -> int:\n        stack = []\n        for a in arr:\n            if not stack or a >= stack[-1]:\n                stack += a,\n            while len(stack) >= 2 and a < stack[-2]:\n                j = stack.pop()\n                stack[-1] = j\n        return len(stack)\n```
[]