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.

Example 1:

Input: n = 4, index = 2,  maxSum = 6
Output: 2
Explanation: nums = [1,2,2,1] is one array that satisfies all the conditions.
There are no arrays that satisfy all the conditions and have nums[2] == 3, so 2 is the maximum nums[2].

Example 2:

Input: n = 6, index = 1,  maxSum = 10
Output: 3

Constraints:

• 1 <= n <= maxSum <= 109
• 0 <= index < n

有界数组中指定下标处的最大值。

给你三个正整数 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 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-value-at-a-given-index-in-a-bounded-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题有两种做法，一种是模拟，一种是二分法。这里我暂时提供一个模拟的做法。这道题的题目不是很直观，题意是需要我们生成一个整形的数组，如果把数组里面的不同的数字看做山的高度的话，这座山应该是从左往右先往上，到达某个顶点，然后一直往下直到最后。那么我们如何确定这个山形数组的峰顶的高度呢，这里首先我们先模拟的是山脚下的第一层，第一层一定能摆满 - 意思是最后的output数组里面的每个元素都起码是1。此时剩下的数字 = maxSum - n。

从第二层（从下往上数）开始，每一层是否能摆满取决于剩下的数（maxSum - n）是多少；同时为了满足题目的另一个条件 abs(nums[i] - nums[i+1]) <= 1，如果当前层摆不满的话，当前层能摆放的个数 = right - left + 1。这里的左和右的边界是从index的位置一点点往外扩散的。

时间O(logM) - M = maxSum - n

空间O(1)

Java实现

 1 class Solution {
 2     public int maxValue(int n, int index, int maxSum) {
 3         int left = index;
 4         int right = index;
 5         int level = 1;
 6         int rest = maxSum - n;
 7         while (left > 0 || right < n - 1) {
 8             int len = right - left + 1;
 9             if (rest >= len) {
10                 rest -= len;
11                 level++;
12                 left = Math.max(0, left - 1);
13                 right = Math.min(n - 1, right + 1);
14             } else {
15                 break;
16             }
17         }
18         level += rest / n;
19         return level;
20     }
21 }

 

LeetCode 题目总结