LeetCode 915.分割数组

LeetCode 915.分割数组

思路

模拟题，两遍遍历，因为要保证左侧区间尽可能小，所以就要找到最左面的适合的点，所以第一遍先从最右边开始记录前缀最小的数，之后再从左往右遍历一遍记录当前最大的前缀，同时将当前最大前缀与下一位的最小前缀比较，如果小于下一位的最小前缀则直接输出即可

代码

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int length = nums.size();
        int min_num[length], max_num=0;
        min_num[length-1] = nums[length-1];
        for(int i=length-2;i>=0;i--)
        {
            min_num[i] = min(min_num[i+1], nums[i]);
        }
        // for(int i=0;i<length;i++)   cout<<min_num[i]<<endl;
        for(int i=0;i<length;i++)
        {
            max_num = max(max_num, nums[i]);
            // cout<<max_num<<endl;
            if(min_num[i+1]>=max_num) return i+1;
        }
        return 0;
    }
};