Monotonic stack solution with detailed explanation
If you are not familiar with monotonic stack, please refer to this first. \n\nUnderstanding how monotonic stack works (build an increasing or decreasing stack b
If you are not familiar with **monotonic stack**, please refer to [this](https://leetcode.com/problems/sum-of-subarray-minimums/discuss/178876/stack-solution-with-very-detailed-explanation-step-by-step) first. \n\nUnderstanding how **monotonic stack** works (build an increasing or decreasing stack based on the input) and what it can do is relatively easy. Unfortunately the hardest part is solution based on monotonic stack is sometimes not intuitive. \n\nHere\'s the thought based on this question. \n\nFirst question, what is the largest number of chunks for an array given the length as `n`? it\'s simple, just `n`, namingly every single element makes up the single-element chunk. For a given array, the largest number of chunks happens when it is increasing and every element is already at the right place.\n`[0, 1, 3, 4]` => `[0, 1], [3], [4]`\n\nSo as long as we are seeing an array that has increasing order, we just keep counting the number of elements in the array. (If you are familiar with **monotonic stack**, have you already smelled that it could be something useful to solve this question?)\n\nLet\'s keeping counting, untill we see the next element `2`. So now the input is `[0, 1, 3, 4, 2]`\nWell what does a suddenly jumped out smaller number mean ?? It means, `2` is not at the right place in the sorted array (we can see `2` actually should sit at the 3rd place in the array right?), **and**  **SOMETHING ELSE** before `2` is also at the wrong place, which we didn\'t realize until we see `2`. So we need to look back. \n\n(While, another hint, we are expecting an increasing order array and we have to look backwards when the order is broken. Does this smell like **monotonic stack**  again?)\n\nSo what exactly are we looking for when we are looking back?\nWe want to find the correct place that `2` should sit at, which means: **We are looking for the largest number that is smaller than `2` in an ascending array**. Why we care about where `2` should be at? because anything between the current position and the should-be position for `2` is not at the correct position that it should be (otherwise how could the poor `2`\'s potion being occupied?). If we can find the elements (including `2`)  that are not at the right position, they need to be put in a chunk, and sorting them inside the chunk is the only way to put them in right place. \n\nSo in this example: `[0, 1, 3, 4, 2]`, we found `1` is the largest number smaller than `2` given our monotonic stack `[0, 1, 3, 4]`. So everything between `3` and `2` (inclusive) is messed up and they `[3, 4, 2]` has to be put in a chunk, so we can sort them back to `[2, 3, 4]` and put them back to the right place. \n\nNormally, we rebuild the monotonic stack from `[0,1, 3, 4]` to `[0, 1, 2]`  by poping out the elements larger than `2` and push `2` back to the queue. However this doesn\'t work for this question. \n\nLet\'s think about what exactly the meaning we want it to be for each element in the increasing stack.\n\nWe want it to mean: **The largest value in each chunk when the chunk cannot be partitioned to smaller ones**. So the number of elements in the stack is exactly the number we are looking for. \n\nSo now the stack became `[0, 1, 4]` instead of `[0, 1, 2]` and each `0` => `[0]`, `1` => `[1]`, `4` => `[3, 4, 2]`. \n\nAnd here\'s the short Python code:\n```\nclass Solution:\n    def maxChunksToSorted(self, arr: List[int]) -> int:\n        stack = []\n        for num in arr:\n            largest = num\n            while stack and stack[-1] > num:\n                largest = max(largest, stack.pop())\n            stack.append(largest)\n        \n        return len(stack)\n```\n\n\n
[]