資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告