不出意外的话, 肯定是不会做了
题目
给你三个正整数 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 \ge 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 \leqslant n \leqslant maxSum \leqslant 10^9$
- $0 \leqslant index < n$
题解
贪心 + 二分查找
根据题意, 需要构造一个长度为 $n$ 的数组 $\textit{nums}$, 所有元素均为正整数, 元素之和不超过 $\textit{maxSum}$, 相邻元素之差不超过 $1$, 且需要最大化 $\textit{nums}[\textit{index}]$. 根据贪心的思想, 可以使 $\textit{nums}[\textit{index}]$ 成为数组最大的元素, 并使其他元素尽可能小, 即从 $\textit{nums}[\textit{index}]$ 开始, 往左和往右, 下标每相差 $1$, 元素值就减少 $1$, 直到到达数组边界, 或者减少到仅为 $1$ 后保持为 $1$ 不变.
根据这个思路, 一旦 $\textit{nums}[\textit{index}]$ 确定后, 这个数组的和 $\textit{numsSum}$ 也就确定了. 并且 $\textit{nums}[\textit{index}]$ 越大, 数组和 $\textit{numsSum}$ 也越大. 据此, 可以使用二分搜索来找出最大的使得 $\textit{numsSum} \leqslant \textit{maxSum}$ 成立的 $\textit{nums}[\textit{index}]$.
代码实现上, 二分搜索的左边界为 $1$, 右边界为 $\textit{maxSum}$. 函数 $\textit{valid}$ 用来判断当前的 $\textit{nums}[\textit{index}]$ 对应的 $\textit{numsSum}$ 是否满足条件. $\textit{numsSum}$ 由三部分组成, $\textit{nums}[\textit{index}]$, $\textit{nums}[\textit{index}]$ 左边的部分之和, 和 $\textit{nums}[\textit{index}]$ 右边的部分之和. $\textit{cal}$ 用来计算单边的元素和, 需要考虑边界元素是否早已下降到 $1$ 的情况.
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/solution/you-jie-shu-zu-zhong-zhi-ding-xia-biao-c-aav4/
来源: 力扣 (LeetCode)
著作权归作者所有. 商业转载请联系作者获得授权, 非商业转载请注明出处.
数学推导
仍然按照方法一的贪心思路, 根据方法一的推导, $\textit{nums}[\textit{index}]$ 左边或者右边的元素和, 要分情况讨论. 记 $\textit{nums}[\textit{index}]$ 为 $\text{big}$, 它离数组的某个边界的距离为 $\textit{length}$. 当 $\text{big} \leqslant \textit{length+1}$ 时, 还未到达边界附近时, 元素值就已经降为 $1$, 并保持为 $1$ 直到到达数组边界, 此时这部分的元素和为 $\dfrac{\textit{big}^2-3\textit{big}}{2}+\textit{length}+1$. 否则, 元素会呈现出梯形的形状, 此时这部分的元素和为 $\dfrac{(2\textit{big}-\textit{length}-1)\times\textit{length}}{2}$.
$\textit{numsSum}$ 由三部分组成, $\textit{nums}[\textit{index}]$,$\textit{nums}[\textit{index}]$ 左边的部分之和, 和 $\textit{nums}[\textit{index}]$ 右边的部分之和. 记 $\textit{nums}[\textit{index}]$ 左边的元素个数为 $\textit{left}= \textit{index}$, 右边的元素个数为 $\textit{right} = n-1-\textit{index}$. 根据对称性, 不妨设 $\textit{left} \leqslant \textit{right}$. 这样一来, $\textit{numsSum}$ 的组成可以用三种情况来表示. 即:
对于前两种情况, 我们可以分别求出上限, 如果上限不超过 $\textit{maxSum}$, 则可以通过解一元二次方程来求出 $\textit{big}$. 否则需要根据第三种情况解一元一次方程来求 $\textit{big}$.
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/solution/you-jie-shu-zu-zhong-zhi-ding-xia-biao-c-aav4/
来源: 力扣 (LeetCode)
著作权归作者所有. 商业转载请联系作者获得授权, 非商业转载请注明出处.
本文链接地址：Leetcode 1802. 有界数组中指定下标处的最大值，英雄不问来路，转载请注明出处，谢谢。
有话想说：那就赶紧去给我留言吧。
文章评论