C++ || Monotonic Stack
Approach\n Describe your approach to solving the problem. \nWe iterate over the array and use a stack to keep track of the highest values encountered. If the cu
# Approach\n<!-- Describe your approach to solving the problem. -->\nWe iterate over the array and use a stack to keep track of the highest values encountered. If the current element is less than the top of the stack, it means we cannot make a new chunk, and we need to merge previous chunks. We pop the stack until the current element is greater than or equal to the top, ensuring all merged chunks maintain order. We then push the maximum value from the merged chunks to preserve the sorting rule.\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxChunksToSorted(vector<int>& arr) {\n        stack<int> st;\n        for(int i=0; i<arr.size(); i++){\n            int maxi = INT_MIN;\n            while(!st.empty() && arr[i]<st.top()){\n                maxi = max(maxi, st.top());\n                st.pop();\n            }\n            if(maxi == INT_MIN) st.push(arr[i]);\n            else st.push(maxi);\n        }\n        return st.size();\n    }\n};\n```
['Array', 'Stack', 'Greedy', 'Monotonic Stack', 'C++']