leetcode 2274. 不含特殊楼层的最大连续楼层数 中等

Alice 管理着一家公司，并租用大楼的部分楼层作为办公空间。Alice 决定将一些楼层作为 特殊楼层 ，仅用于放松。

给你两个整数 bottom 和 top ，表示 Alice 租用了从 bottom 到 top（含 bottom 和 top 在内）的所有楼层。另给你一个整数数组 special ，其中 special[i] 表示  Alice 指定用于放松的特殊楼层。

返回不含特殊楼层的 最大 连续楼层数。

示例 1：

输入：bottom = 2, top = 9, special = [4,6]
输出：3
解释：下面列出的是不含特殊楼层的连续楼层范围：
- (2, 3) ，楼层数为 2 。
- (5, 5) ，楼层数为 1 。
- (7, 9) ，楼层数为 3 。
因此，返回最大连续楼层数 3 。

示例 2：

输入：bottom = 6, top = 8, special = [7,6,8]
输出：0
解释：每层楼都被规划为特殊楼层，所以返回 0 。

提示

• 1 <= special.length <= 10^5
• 1 <= bottom <= special[i] <= top <= 10^9
• special 中的所有值 互不相同

分析：可以在排序前将 bottom−1 和 top+1 也放入给定的数组 special 按照升序排序。这样一来任意相邻两个元素之间的楼层就都不是特殊楼层。如果相邻的两个元素分别为 x,y，那么非特殊楼层的数量即为 y−x−1。记录最大值即可。

int cmp(const void *a,const void *b)
{int *aa=(int*)a;int *bb=(int*)b;return *aa-*bb;
}int maxConsecutive(int bottom, int top, int* special, int specialSize) {int temp[specialSize+2];temp[specialSize]=bottom-1,temp[specialSize+1]=top+1;int fb=0,ft=0;for(int i=0;i<specialSize;++i){temp[i]=special[i];if(special[i]==bottom)fb=1;if(special[i]==top)ft=1;}qsort(temp,specialSize+2,sizeof(int),cmp);int ans=-1,l=specialSize+2;for(int i=1;i<l;++i){int cnt=temp[i]-temp[i-1]-1;ans=fmax(ans,cnt);}return ans;
}