力扣(LeetCode)1802. 有界数组中指定下标处的最大值(C++)
贪心+二分查找
贪心性质：对于数组中确定位置index的数，要使nums[index]最大，等于使得整个数组之和最小。
提示 ：数组相邻元素之差的绝对值小于1，为了数组之和最小，从index往左，形成公差为1的递减序列；从index往右，形成公差为1的递减序列。
考虑枚举nums[index]的值，从1开始。从小到大枚举，数组之和第一次大于maxSum时，上一次枚举的nums[index]的值，即为所求。时间复杂度
O
(
m
a
x
S
u
m
)
O(maxSum)
O(maxSum) ，
T
L
E
TLE
TLE。
二分查找优化枚举。时间复杂度 O ( l o g m a x S u m ) O(log\ maxSum) O(log maxSum) 。
题目描述
代码分析
二分查找边界 : l、r是二分左右数值，mid是中间值。
数组位置 ：posl、posr是index影响范围的左边界、右边界。影响范围之内，即[posl,posr]，采用等差数列求和；影响范围之外，即[0,posl)和(posr,n-1]，数字均是1。
数组边界：numl、numr是index影响范围的左边界的值、右边界的值。
数组之和：suml、sumr分别是[0,posl)的数组之和、(posr,n-1]的数组之和。
核心代码
class Solution {
public:
int maxValue(int n, int index, int maxSum) {
int l = 1 , r = maxSum;
while(l<=r){
int mid = l +(r-l>>1);
int posl = max(0,index - (mid - 1));
int posr = min(n-1,index + mid - 1);
int numl = max(1,mid - (index - posl));
int numr = max(1,mid - (posr - index));
long long suml ,sumr;
if(index == posl) suml = 0;
else suml = (long long)(numl + mid-1) * (index - posl) /2;
if(index == posr) sumr = 0;
else sumr = (long long)(mid-1+numr) * (posr - index) /2 ;
long long ans = (posl-0) + (n-1 - posr) + suml + sumr + mid;
if(ans<=maxSum) l = mid+1;
else r = mid - 1;
}
return l-1;
}
};
- 时间复杂度 : O ( l o g m ) O(logm) O(logm) ， m = m a x S u m m=maxSum m=maxSum 是数组之和的最大限制，二分查找的时间复杂度 O ( l o g m ) O(logm) O(logm) 。
- 空间复杂度 : O ( 1 ) O(1) O(1) ， 只使用常量级空间 。
AC
致语
- 理解思路很重要
- 读者有问题请留言，清墨看到就会回复的。
- 读者加油，能写出来的！