[c++] Using Stack with O(n) space and time complexity. With 7 lines. 4ms. Beats 100%
We can treat each chunk as a range with (max value, min value) as a pair. Because we want to find the longest chunks, we need to treat each number as a range at
We can treat each chunk as a range with (max value, min value) as a pair. Because we want to find the longest chunks, we need to treat each number as a range at first. ( 5: treat as range(5,5) )We use a stack to store these ranges. We need to merge the current range and previous range when current range\'s min value < previous range\'s max value. The answer is the number of ranges stored in the stack.\n\n\nFor example: \n[2,1,3,4,4]\nWe first meet 2, set is as range with max and min value (2 , 2)\nWhen we encounter 1 as (1,1), current range (1,1), the min value 1 is smaller than previous (2,2) max value 2. So we need to merge these two ranges as (2,1). For (3,3), min value 3 is larger than (2,1) max value 2, so we keep it. In the same way, we keep (4,4) and (4,4). Finally, in our stack, it is (2,1),(3,3),(4,4),(4,4). So the answer is 4.\n\n```\nclass Solution {\npublic:\n    int maxChunksToSorted(vector<int>& arr) {\n        stack<pair<int,int>>st;\n        for(int i=0;i<arr.size();i++) {\n            pair<int,int> it=make_pair(arr[i],arr[i]);\n            while( (!st.empty()) && (st.top().first>it.second) ) {\n                auto pre=st.top();\n                st.pop();\n                it.second = min(pre.second,it.second);\n                it.first = max(pre.first, it.first);\n            }\n            st.push(it);\n        }\n        return st.size()\n    }\n};\n```\n\n\nThanks for @**einhorn** suggestion.  We do not need to keep track of the min value. We just need to know the previous max value.\n```\n   int maxChunksToSorted(vector<int>& arr) {\n        stack<int>st;\n        for(int i=0;i<arr.size();i++) {\n            int curmax=st.empty() ? arr[i]: max(st.top(),arr[i]);\n            while( (!st.empty()) && (st.top()>arr[i]) ) st.pop();\n            st.push(curmax);\n        }\n        return st.size();\n    }\n```\n\n
[]