数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学C++ 中包含单个数字的最长区间
假设我们有一个名为 nums 的不同整数列表。我们必须找到最大区间（包含）[start, end] 的大小，该区间在 nums 中最多包含一个数字。
因此，如果输入类似于 nums = [10, 6, 20]，则输出将为 99990，因为最大区间为 [11, 100000]，它仅包含 20。
为了解决这个问题，我们将遵循以下步骤：
ret := -inf
end := 100000
prev := 1
对数组 nums 进行排序
n := nums 的大小
对于初始化 i := 0，当 i < nums 的大小，更新（i 增加 1），执行：
如果 i + 1 < n，则：
high := nums[i + 1] - 1
否则
high := end
如果 i - 1 >= 0，则：
low := prev + 1
否则
low := prev
prev := nums[i]
ret := high - low + 1 和 ret 的最大值
返回 ret
让我们看看下面的实现以获得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<int> &nums) {
int ret = INT_MIN;
int end = 100000;
int prev = 1;
sort(nums.begin(), nums.end());
int n = nums.size();
int low, high;
for (int i = 0; i < nums.size(); i++) {
if (i + 1 < n) {
high = nums[i + 1] - 1;
} else
high = end;
if (i - 1 >= 0) {
low = prev + 1;
} else
low = prev;
prev = nums[i];
ret = max(high - low + 1, ret);
}
return ret;
}
};
main() {
Solution ob;
vector<int> v = {10, 6, 20};
cout << (ob.solve(v));
}输入
{10, 6, 20}输出
99990
更新于：2020年9月2日
117 次查看
广告