LeetCode —— 覆盖问题

1893. 检查是否区域内所有整数都被覆盖

图片说明
图片说明

思路一:先排序,后检查

class Solution {
    public boolean isCovered(int[][] ranges, int left, int right) {
        //1.先按照数组第一个数升序排序
        Arrays.sort(ranges , (a,b) -> (a[0] - b[0]));
        int i = 0;
        //2.找到左端点所在数组,更新左端点为数组第二个数
        while( i < ranges.length ){
            int l = ranges[i][0];
            int r = ranges[i][1];
            if(left >= l && left <= r){
                left = r + 1;
            }
            i++;
        }
        //3.判断【更新后的左端点】是否超过【右端点】
        return left > right;
    }
}

思路二:差分数组+前缀和

1.对判断区域range内所有整数计算覆盖的区间数量

2.用差分数组 \textit{diff}diff 维护相邻两个整数的被覆盖区间数量变化量

全部评论

相关推荐

点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务