maximum-value-at-a-given-index-in-a-bounded-array

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given three positive integers:&nbsp;<code>n</code>, <code>index</code>, and <code>maxSum</code>. You want to construct an array <code>nums</code> (0-indexed) that satisfies the following conditions:

<ul>
	<li><code>nums.length == n</code></li>
	<li><code>nums[i]</code> is a positive integer where <code>0 &lt;= i &lt; n</code>.</li>
	<li><code>abs(nums[i] - nums[i+1]) &lt;= 1</code> where <code>0 &lt;= i &lt; n-1</code>.</li>
	<li>The sum of all the elements of <code>nums</code> does not exceed <code>maxSum</code>.</li>
	<li><code>nums[index]</code> is maximized.</li>
</ul>

Return <code>nums[index]</code> of the constructed array.

Note that <code>abs(x)</code> equals <code>x</code> if <code>x &gt;= 0</code>, and <code>-x</code> otherwise.

&nbsp;
Example 1:

<pre>
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].
</pre>

Example 2:

<pre>
Input: n = 6, index = 1, maxSum = 10
Output: 3
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= maxSum &lt;= 109</code></li>
	<li><code>0 &lt;= index &lt; n</code></li>
</ul>

maxValue

Maximum Value at a Given Index in a Bounded Array

Greedy

Binary Search

给你三个正整数 <code>n</code>、<code>index</code> 和 <code>maxSum</code> 。你需要构造一个同时满足下述所有条件的数组 <code>nums</code>（下标 从 0 开始 计数）：

<ul>
	<li><code>nums.length == n</code></li>
	<li><code>nums[i]</code> 是 正整数 ，其中 <code>0 &lt;= i &lt; n</code></li>
	<li><code>abs(nums[i] - nums[i+1]) &lt;= 1</code> ，其中 <code>0 &lt;= i &lt; n-1</code></li>
	<li><code>nums</code> 中所有元素之和不超过 <code>maxSum</code></li>
	<li><code>nums[index]</code> 的值被 最大化</li>
</ul>

返回你所构造的数组中的 <code>nums[index]</code> 。

注意：<code>abs(x)</code> 等于 <code>x</code> 的前提是 <code>x &gt;= 0</code> ；否则，<code>abs(x)</code> 等于 <code>-x</code> 。

 

示例 1：

<pre>输入：n = 4, index = 2, maxSum = 6
输出：2
解释：数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。
</pre>

示例 2：

<pre>输入：n = 6, index = 1, maxSum = 10
输出：3
</pre>

 

提示：

<ul>
	<li><code>1 &lt;= n &lt;= maxSum &lt;= 109</code></li>
	<li><code>0 &lt;= index &lt; n</code></li>
</ul>