# 0915. Partition Array into Disjoint Intervals
###### tags: `Leetcode` `Microsoft` `Medium`
Link: https://leetcode.com/problems/partition-array-into-disjoint-intervals/
## 思路
### 思路一 O(N)&O(N)
用两个array leftMax, rightMin 记录
leftMax[i]表示从第0个元素到第i个元素里面的最大值
rightMin[i]表示从第length-1个元素到第i个元素里面的最小值
如果对于某个i leftMax[i]<rightMin[i], 则i+1就是答案

**空间优化**不需要存leftMax，直接用回圈跟rightMin比较即可
### 思路二 O(N)&O(1)
因为长度不会为0，所以left array里面一定有nums[0]，在后面找小于nums[0]的数，它一定要包含在left array里面，这时left array里面的最大值就会更新（possible Max->current Max),以此循环

## Code
### 思路一

class Solution {
    public int partitionDisjoint(int[] nums) {
        int[] leftMax = new int[nums.length];
        leftMax[0] = nums[0];
        int[] rightMin = new int[nums.length];
        rightMin[nums.length-1] = nums[nums.length-1];
        for(int i = 1;i < nums.length;i++){
            leftMax[i] = Math.max(leftMax[i-1],nums[i]);
        }
        for(int i = nums.length-2;i >= 0;i--){
            rightMin[i] = Math.min(rightMin[i+1],nums[i]);
        }
        for(int i = 0;i < nums.length-1;i++){
            if(leftMax[i]<=rightMin[i+1]){
                return i+1;
            }
        }
        return nums.length-2;
    }
}