本文涉及的基础知识点
C++二分查找
LeetCode 1802. 有界数组中指定下标处的最大值
给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums(下标 从 0 开始 计数):
nums.length == n
nums[i] 是 正整数 ,其中 0 <= i < n
abs(nums[i] - nums[i+1]) <= 1 ,其中 0 <= i < n-1
nums 中所有元素之和不超过 maxSum
nums[index] 的值被 最大化
返回你所构造的数组中的 nums[index] 。
注意:abs(x) 等于 x 的前提是 x >= 0 ;否则,abs(x) 等于 -x 。
示例 1:
输入:n = 4, index = 2, maxSum = 6
输出:2
解释:数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。
示例 2:
输入:n = 6, index = 1, maxSum = 10
输出:3
提示:
1 <= n <= maxSum <= 109
0 <= index < n
C++二分查找
二分查找类型:寻找尾端
Check函数范围:[1,1e9]
Check函数:
假定nums[index]为mid,求其和的最小值sum 。return sum <= maxSum。
时间复杂度: O(log1e9),其中Check 函数时间复杂度O(1)
如果nums[index]是mid,则
nums[index-1]和nums[index+1] 是 mid-1
⋮ \vdots ⋮
left = index - (mid -1)和right = index+(mid-1)是1 。
其它都是1。
注意要处理越界,left小于0取0;大于等于n,取n-1。
代码
核心代码
template<class INDEX_TYPE>
class CBinarySearch
{
public:
CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}
template<class _Pr>
INDEX_TYPE FindFrist( _Pr pr)
{
auto left = m_iMin - 1;
auto rightInclue = m_iMax;
while (rightInclue - left > 1)
{
const auto mid = left + (rightInclue - left) / 2;
if (pr(mid))
{
rightInclue = mid;
}
else
{
left = mid;
}
}
return rightInclue;
}
template<class _Pr>
INDEX_TYPE FindEnd( _Pr pr)
{
int leftInclude = m_iMin;
int right = m_iMax + 1;
while (right - leftInclude > 1)
{
const auto mid = leftInclude + (right - leftInclude) / 2;
if (pr(mid))
{
leftInclude = mid;
}
else
{
right = mid;
}
}
return leftInclude;
}
protected:
const INDEX_TYPE m_iMin, m_iMax;
};
class Solution {
public:
int maxValue(int n, int index, int maxSum) {
auto Check = [&](int mid) {
long long left = max(0,index - (mid - 1));
long long right = min(n-1,index + (mid - 1));
long long sum = left + (n - right-1) + mid;
long long cnt1 = index - left;
sum += (mid - cnt1 + mid - 1) * cnt1 / 2;
long long cnt2 = right - index;
sum += (mid - cnt2 + mid - 1) * cnt2 / 2;
return sum <= maxSum;
};
return CBinarySearch<int>(1, 1'000'000'000).FindEnd(Check);
}
};
单元测试
int n, index, maxSum;
TEST_METHOD(TestMethod1)
{
n = 1, index = 0, maxSum = 6;
auto res = Solution().maxValue(n, index, maxSum);
AssertEx(6, res);
}
TEST_METHOD(TestMethod11)
{
n = 4, index = 2, maxSum = 6;
auto res = Solution().maxValue(n, index, maxSum);
AssertEx(2, res);
}
TEST_METHOD(TestMethod12)
{
n = 6, index = 1, maxSum = 10;
auto res = Solution().maxValue(n, index, maxSum);
AssertEx(3, res);
}