[Python] simple and faster than 96.5%
There is one rule to be maintained in any correct split to chunks\n The max number in every chunk should be <= than the max number in the following chunk\n\nThe
There is one rule to be maintained in any correct split to chunks\n* The max number in every chunk should be <= than the max number in the following chunk\n\nThen, we can build the greedy O(n) algorithm to iterate over nums in array and maintain the sequence of max numbers in chunks on each step (i.e. on step **i** we will have the sequence for elements with indices **0...i**)\nIn order to do that we will maintain a monotonic non-decreasing stack.\nFor each num in array:\n1. Initialize **m=num**\n2. Num is in the same chunk as all elements of stack for which **num < stack[i]**. Stack is monotonic non-decreasing (stack[0] <= stack[1] <= ... <= stack[-1]), so we can pop from the end of stack until we find that **num < stack[-1]**. Save max of the new last chunk to **m**.\n3. Append **m** to the stack\n\nThe algorithm is correct because:\nIf we popped any elements on step 2 - then **m** is the max element of the last chunk.\nOtherwise **m** is **num**, which is the max element of the new last chunk.\n\n```\nclass Solution:\n    def maxChunksToSorted(self, arr: List[int]) -> int:\n        stack = []\n        for num in arr:\n            m = num\n            while stack and num < stack[-1]:\n                m = max(m, stack.pop())\n            stack.append(m)\n        return len(stack)\n```
['Greedy', 'Monotonic Stack', 'Python']