Java | O(n) | A Stack Solution
Track the max and push it onto the stack if it is no less than the current max (meaning it is possible for it to be the start of a valid chuck).\n- If the curre
- Track the max and push it onto the stack if it is no less than the current max (meaning it is *possible* for it to be the start of a valid chuck).\n- If the current element is greater than the top of the stack, pop it off because it can\'t be a valid check (merge operation).\n- Initialize max to `-1` as the start.\n\n#### How does it work? \nLogically, the current element can **not** be less than the max recorded.\nBecause the size of stack is the number of valid chucks, we have to pop all invaild ones off.\nAlso, it is only possible for an element to be a start of a valid chuck when it is at least as large as the current max element, \nif it is not, then it belong to the previous chuck, so it shouldn\'t be pushed onto the stack.\n\n#### Commentary\nI think it is a pretty solution. Took me a bit of thinking to get it right. \n```Java\nclass Solution {\n    public int maxChunksToSorted(int[] arr) {\n        Deque<Integer> stack = new ArrayDeque<>();\n        int max = -1;\n        for (int i = 0; i < arr.length; i++){\n            while(!stack.isEmpty() && arr[i]<stack.peek()){ // don\'t pop if they are ==\n                stack.pop();\n            }\n            if (arr[i]>=max){\n                stack.push(max);\n            }\n            max=Math.max(arr[i],max);\n        }\n        return stack.size();\n    }\n}\n```
['Stack', 'Java']