56.md

56. 合并区间

[[10,14],[25,35],[17,27],[33,44],[4,15],[3,22],[66,90],[72,89]]  <- 输入

[[3,22],[4,15],[10,14],[17,27],[25,35],[33,44],[66,90],[72,89]]  <- 按首数字排序后

stack: 3,22  <- 利用栈合并重叠区间，执行到 [10,14] 时

stack: 3,44  <- 执行到 [33,44] 时

stack: 3,44,66,90  <- 执行完时

[[3,44],[66,90]]   <- 转换为二维数组

思路

• 标签：栈
• 需要先整体排序，如果没有想到这个，基本上没法做了
• 再需要利用栈，利用跟栈顶元素比较来判断是否重叠
  • 将数组第一组元素作为初始值构建一个栈
  • 栈顶元素依次跟数组其他元素比较，如果左侧元素大于栈顶元素，入栈
  • 如果左侧元素小于等于栈顶元素，且右侧元素也小于等于栈顶元素，说明当前区间被包含
  • 如果左侧元素小于等于栈顶元素，右侧元素大于栈顶元素，那么就弹出栈顶元素，压入右侧元素
• 时间复杂度：O(n)，不算排序
• 空间复杂度：O(n)？，额外需要一个栈，栈的高度小于 N，但不是一个常数

代码

## Python3
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 0:
            return []
        intervals.sort()
        stack = [intervals[0][0], intervals[0][1]]
        for i in range(1, len(intervals)):
            if intervals[i][0] <= stack[-1]:
                if intervals[i][1] <= stack[-1]:
                    continue
                else:
                    stack.pop()
                    stack.append(intervals[i][1])
            else:
                stack.append(intervals[i][0])
                stack.append(intervals[i][1])
        res = []
        for i in range(0, len(stack), 2):
            res.append([stack[i], stack[i + 1]])
        return res

// Java
class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][0];
        }
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // lambda 表达式
        Stack<Integer> stack = new Stack<Integer>(){{add(intervals[0][0]);add(intervals[0][1]);}};
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= stack.peek()) {
                if (intervals[i][1] <= stack.peek()) {
                    continue;
                } else {
                    stack.pop();
                    stack.push(intervals[i][1]);
                }
            } else {
                stack.push(intervals[i][0]);
                stack.push(intervals[i][1]);
            }
        }
        int[][] res = new int[stack.size() / 2][2];
        for (int i = 0; i < stack.size(); i++) {
            if (i % 2 == 0) {
                res[i/2][0] = stack.get(i);
            } else {
                res[i/2][1] = stack.get(i);
            }
        }
        return res;
    }
}

二维数组：

res = [[3,44],[66,90]]

3, 44
66,90

res[0] = [3,44]
res[0][1] = 44
res[1][0] = 66

Arrays 排序二维数组：

        Integer[][] intervals = new Integer[10][10];
        Arrays.sort(intervals, new Comparator<Integer[]>() {
            @Override
            //arguments to this method represent the arrays to be sorted   
            public int compare(Integer[] o1, Integer[] o2) {
                //get the item ids which are at index 0 of the array
                Integer itemIdOne = o1[0];
                Integer itemIdTwo = o2[0];
                // sort on item id
                return itemIdOne.compareTo(itemIdTwo);
            }
        });