401. Best Minimum per Width
A city planner has a street with n consecutive plots, and nums[i] is the building height allowed on plot i. For a block of w neighbouring plots, the limiting height is the smallest allowed height inside it, because one roof must cover the whole block at the same level.
For every width w from 1 to n, find the best limiting height over all blocks of exactly w adjacent plots, that is, the maximum over all blocks of that width of the minimum inside the block. Return an array of length n whose entry at index w - 1 is that value. Checking every block directly takes at least O(n^2) time.
Example 1
- Input:
- nums = [6,2,5,4,1,3]
- Output:
- [6,4,2,2,1,1]
- Explanation:
Width 1: best single plot is 6. Width 2: block pairs have minimums 2, 2, 4, 1, 1, so 4. Width 3 and 4: best minimum is 2. Widths 5 and 6 include the plot with 1.
Example 2
- Input:
- nums = [0,9,9,3]
- Output:
- [9,9,3,0]
- Explanation:
Width 1 and 2 can both use the pair of 9s. Width 3 must include either the 0 or ends at the 3, so the best minimum is 3, and the full block contains 0.
Constraints
1 ≤ nums.length ≤ 1500
0 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)