Show problems as
Classic problem #1846MediumArrayGreedySorting

Maximum Element After Decreasing and Rearranging

Real-world version: Shaved Course Wall
Tracked in this browser only
Read Maximum Element After Decreasing and Rearranging on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A mason has one block per entry of blocks, and blocks[i] is how many courses of brick block i currently stands. Before building, the mason may apply either operation as often as wanted, in any order:

  • shave a block down to any smaller whole number of courses, never below 1 and never taller than it already is;
  • swap two blocks, so the blocks may end up in any order along the wall.

The finished wall, read left to right, must satisfy both rules:

  • the leftmost block stands exactly 1 course;
  • neighbouring blocks differ by at most 1 course.

Every block must be used. Return the largest number of courses any block can stand in a finished wall.

Examples

Example 1

Input
blocks = [2, 2, 1, 1, 3]
Output
3

Shaving the two blocks of three courses down and ordering the wall as 1, 1, 2, 2, 3 obeys both rules, and its tallest block stands 3 courses.

Example 2

Input
blocks = [1, 1, 5]
Output
2

Ordering the wall as 1, 1, 2 after shaving the tall block from 5 courses to 2 obeys both rules, and its tallest block stands 2 courses.

Example 3

Input
blocks = [1000000000, 1, 1000000000]
Output
3

Shaving the two tall blocks to 2 and 3 courses and ordering the wall as 1, 2, 3 obeys both rules, and its tallest block stands 3 courses.

Constraints

  • 1 <= blocks.length <= 10^5
  • 1 <= blocks[i] <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def tallest_after_shaving(blocks: list[int]) -> int:
Java
public int tallestAfterShaving(int[] blocks)

More on the same topics