Leetcode第915题：分割数组（Partrition Array Into Disjoint Intervals）

解题思路

最终的是将一个数组分为两个数组：左数组和右数组。这两个数组满足：

• 左数组的最大值小于右数组的任何值。需要一个变量left_max来记录左数组的最大值。
• 左数组长度尽可能小。使用变量idx记录满足条件的数组位置。

左数组右边的值较小，则右边该值一定会划分到左数组。此时需要更新idx的位置，当遍历完整个数组后，idx的位置就是左数组的最后一个元素位置，右数组的所有值都大于left_max。

核心代码如下：

class Solution {
public:
    int partitionDisjoint(vector<int>& num) {
        int len = num.size();
        int idx = 0;    //标记返回位置
        int max = num[0];   //记录当前循环最大值
        int left_max = max; //记录左边数组的最大值
        for (int i=0; i < len; i++) {
            if (left_max > num[i]) {
                idx = i;
                left_max = max;     //idx位置右边有值更小，更新idx到该值
            }
            max = std::max(max, num[i]);     //右数组值更大，更新最大值（截止到当前位置i，包括左右数组）
        }
        //循环结束后，max值是整个数组最大值，idx所在位置右边值都比num[idx]大

        return idx+1;
    }
};