915.分割数组

链接：915.分割数组
难度：Medium
标签：数组
简介：在完成这样的分组后返回 left 的 长度 。

题解 1 - cpp

• 编辑时间：2022-10-24
• 执行用时：140ms
• 内存消耗：91.9MB
• 编程语言：cpp
• 解法介绍：一次遍历，维护左边的最大值。

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int n = nums.size(), cur_max = nums[0], ans = 1, ans_max = nums[0];
        for (int i = 1; i < n; i++) {
            cur_max = max(cur_max, nums[i]);
            if (nums[i] < ans_max) {
                ans_max = cur_max;
                ans = i + 1;
            }
        }
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2022-10-24
• 执行用时：732ms
• 内存消耗：136.2MB
• 编程语言：cpp
• 解法介绍：维护有序序列。

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int n = nums.size();
        map<int, int> m1, m2;
        m1[nums[0]]++;
        for (int i = 1; i < n; i++) m2[nums[i]]++;
        int idx = 1;
        while (m1.crbegin()->first > m2.cbegin()->first) {
            m1[nums[idx]]++;
            m2[nums[idx]]--;
            if (m2[nums[idx]] == 0) m2.erase(nums[idx]);
            ++idx;
        }
        return idx;
    }
};