768.最多能完成排序的块II

链接：768.最多能完成排序的块II
难度：Hard
标签：栈、贪心、数组、排序、单调栈
简介：我们最多能将数组分成多少块？。

题解 1 - cpp

• 编辑时间：2022-08-15
• 执行用时：8ms
• 内存消耗：11.8MB
• 编程语言：cpp
• 解法介绍：单调栈，每次意味着左边块中所有的元素都小于右边块，如果不满足则合并。

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        vector<int> s;
        for (auto &num : arr) {
            if (s.empty() || s[s.size() - 1] <= num) {
                s.push_back(num);
            } else {
                int num_max = s[s.size() - 1];
                while (s.size() && s[s.size() - 1] > num) s.pop_back();
                s.push_back(num_max);
            }
        }
        return s.size();
    }
};