区间 --面试经典150题

汇总区间

做题过程

主要是怎么处理输出比较麻烦，本身没有什么算法。

算法概述

本题要求为将给出的整数数组汇总为一些连续区间。只需要一次遍历即可。

时间复杂度为O(n)
空间复杂度为O(1)

JAVA

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ret=new ArrayList<String>();
        int i=0;
        int n=nums.length;
        // 一次遍历
        while(i<n){
            // 区间左边界
            int low=i;
            i++;
            // 连续区间
            while(i<n&&nums[i]==nums[i-1]+1){
                i++;
            }
            // 区间右边界
            int high=i-1;
            // 用左边界初始化
            StringBuffer temp=new StringBuffer(Integer.toString(nums[low]));
            // 判断是单一元素还是连续区间
            if(low<high){
                temp.append("->");
                temp.append(Integer.toString(nums[high]));
            }
            ret.add(temp.toString());
        }
        return ret;
    }
}

总结

这种题目主要在于能不能熟练使用StringBuffer这样的类（如果是C++就应该使用vector<string>，以及如何组织代码结构。

插入区间(medium)

做题过程

肯定是模拟，但感觉分类讨论蛮多的，需要一些其他技巧进行优化。

算法概述

原题

本题要求为给定一个区间以及一个区间为元素的升序数组，插入给定区间（重叠则合并）。

时间复杂度为O(n)
空间复杂度为O(1)

JAVA

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        // 解包
        int left = newInterval[0];
        int right = newInterval[1];
        // 标记是否已插入，避免重复判断
        boolean placed = false;

        List<int[]> ansList = new ArrayList<int[]>();

        for (int[] interval : intervals) {
            if (interval[0] > right) {
                // 在插入区间的右侧且无交集
                if (!placed) {
                    ansList.add(new int[]{left, right});
                    placed = true;                    
                }
                ansList.add(interval);
            } else if (interval[1] < left) {
                // 在插入区间的左侧且无交集
                ansList.add(interval);
            } else {
                // 与插入区间有交集，计算它们的并集
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        // 处理边界情况
        if (!placed) {
            ansList.add(new int[]{left, right});
        }
        // 将列表转换回基本数组
        int[][] ans = new int[ansList.size()][2];
        for (int i = 0; i < ansList.size(); ++i) {
            ans[i] = ansList.get(i);
        }
        return ans;
    }
}

总结

分类如下：

当前遍历区间在目标区间右侧（无并集）：插入目标区间以及当前遍历区间
当前遍历区间在目标区间左侧（无并集）：只插入当前遍历区间
当前遍历区间与目标区间重叠（有并集）：由比较得出新的区间再插入

除此之外，还需注意处理在末尾插入的情况，因为第二个分类并不处理尾部插入的逻辑，所以这里需要一个 标记哨兵 。

用最少数量的箭引爆气球

做题过程

还是排序以及合并区间的问题。

算法概述

原题

本题要求为计算需要多少个元素能够代表所有区间（重叠的区间可以用一个相同的值来代表）。需要运用的是 排序以及贪心 。

时间复杂度为O(nlogn)：主要是排序
空间复杂度为O(logn)：容器类排序所需要的栈空间

JAVA

class Solution {
    public int findMinArrowShots(int[][] points) {
        if(points.length==0) return 0;

        Arrays.sort(points, new Comparator<int[]>(){
            // 升序（右边界排序）
            public int compare(int[] point1,int[] point2){
                if(point1[1]>point2[1]) return 1;
                if(point1[1]<point2[1]) return -1;
                // 当值相等，优先级也相等
                else return 0;
            }
        });
        // 把问题降维为一个不断移动的指针，不再需要其他动态的数据结构
        int pos=points[0][1];
        int ans=1;
        // 贪心
        for(int[] balloon: points){
            // 当新的左边界比当前指针小，说明需要新箭
            if(balloon[0]>pos){
                // 指针直接跳至右边界
                pos=balloon[1];
                ++ans;
            }
        }
        return ans;
    }
}

总结

对于数字相关的问题，需要熟练掌握自定义比较器相关的方法。区间相关问题的优化路径在于在排序后如何省去多余的边界比较，比如此处就不再需要比较右边界，如何分工左右边界是需要思考与理解的。