有界数组中指定下标处的最大值【LC1802】
You are given three positive integers: n, index, and maxSum. You want to construct an array nums (0-indexed) that satisfies the following conditions:
- nums.length == n
- nums[i] is a positive integer where 0 <= i < n.
- abs(nums[i] - nums[i+1]) <= 1 where 0 <= i < n-1.
- The sum of all the elements of nums does not exceed maxSum.
- nums[index] is maximized.
Return nums[index] of the constructed array.
Note that abs(x) equals x if x >= 0, and -x otherwise.
按专题训练效果就是不错
- 思路：
。由于当指定下标处的数值越大，数组总和也越大，因此可以通过二分查找搜索指定下标处的最大值。
- 因为数组中的数值有要求：相邻元素的绝对值不超过1，数组中的元素均大于等于1，并尽可能使指定下标处的元素最大
- 当数组和一定时，要使指定下标处的数值最大，应以该位置为中心，相邻位置以1为间隔梯度下降，直至数值等于1【贪心获得数组和】
- 因此指定下标的数值固定时，数组总和固定【单调性】
。因此可以将题意转化为当数组总和小于等于maxSum时，寻找指定下标处数值的最大值y，二分查找的下限为1，上限为maxSum
- 实现
。当二分查找指定下标处的数值y时，需要判断数组总和是否小于等于maxSum，如果数组总和小于等于maxSum，那么我们可以增大最大数值；如果不能，那么减小最大数值
class Solution { public int maxValue(int n, int index, int maxSum) { if (maxSum == n) return 1; int l = 1, r = maxSum; int ans = 0; while (l <= r){ int mid = (l + r) / 2; if (check(mid, index, n, maxSum)){ ans = mid; l = mid + 1; }else{ r = mid - 1; } } return ans; } public boolean check(int max, int index, int n, int maxSum){ int sum = max; int l = index, r = index; int cur = max; while (--l >= 0 && --cur > 1){ sum += cur; if (sum > maxSum){ return false; } } sum += l + 1; cur = max; while (++r < n && --cur > 1){ sum += cur; if (sum > maxSum){ return false; } } sum += (n - r); return sum <= maxSum; } }
。复杂度
- 时间复杂度：O(nlogC)，n 是数组的长度，C是maxSum。求出数组和需要的时间复杂度为O(n)，二分查找的时间复杂度是O(logC)
- 空间复杂度：O(1)
- 优化判断过程：根据等差数列性质求和
class Solution { public int maxValue(int n, int index, int maxSum) { int left = 1, right = maxSum; while (left < right) { int mid = (left + right + 1) / 2; if (valid(mid, n, index, maxSum)) { left = mid; } else { right = mid - 1; } } return left; } public boolean valid(int mid, int n, int index, int maxSum) { int left = index; int right = n - index - 1; return mid + cal(mid, left) + cal(mid, right) <= maxSum; } public long cal(int big, int length) { if (length + 1 < big) { int small = big - length; return (long) (big - 1 + small) * length / 2; } else { int ones = length - (big - 1); return (long) big * (big - 1) / 2 + ones; } } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/solutions/2042360/you-jie-shu-zu-zhong-zhi-ding-xia-biao-c-aav4/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O(logC)，n是数组的长度，C是maxSum。求出数组和需要的时间复杂度为O(1)，二分查找的时间复杂度是O(logC)
- 空间复杂度：O ( 1 )
