力扣 57 插入区间

题意：给一个区间数组，和一个区间，把那个区间插入区间数组

思路：遍历每一个interval

1. 如果当前interval的结束时间比newInterval的开始时间早，把interval加入stack
2. 如果当前interval的开始时间比newInterval的结束时间晚，把newInterval加入stack，并更新newInterval
3. 其他情况更新newInterval
4. 遍历结束后把newInterval加入stack
5. 从stack中构建res，并返回

思想：利用堆栈

复杂度：时间O（n)，空间O(n)

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        Stack<int[]> stack = new Stack();
        for(int[] interval: intervals) {
            if(interval[1] < newInterval[0]) {
                stack.add(interval);
            } else if(newInterval[1] < interval[0]) {
                stack.add(newInterval);
                newInterval = interval;
            } else {
                newInterval[0] = Math.min(interval[0], newInterval[0]);
                newInterval[1] = Math.max(interval[1], newInterval[1]);
            }
        }
        stack.add(newInterval);
        int[][] res = new int[stack.size()][2];
        int cnt = stack.size() - 1;
        while(!stack.isEmpty()) {
            res[cnt--] = stack.pop();
        }
        return res;
    }
}