Best Minimum for Every Window Size
You get an integer array nums of length n.
A window of size w is a group of w elements that sit next to each other in nums. Every window has a minimum (its smallest value).
For each window size w from 1 to n, look at every window of that size and take the largest of their minimums.
Return an array of length n. The value at position w - 1 is the answer for window size w.
Hint
Checking every window of every size is O(n³), or O(n²) with care. Think about it from the other side: for each element, find the widest window in which it is the minimum. That window ends just before the nearest smaller element on the left and on the right, and a stack finds both for all elements in O(n). Each element is then a candidate answer for that width. A larger window cannot have a better answer than a smaller one, so finish by passing from right to left and keeping the larger value.
Examples
Example 1
- Input:
- [4,8,2,7,6]
- Output:
- [8,6,2,2,2]
Size 1: the largest single value is 8. Size 2: windows have minimums 4, 2, 2, 6, so the best is 6. Every window of size 3 or more contains the 2, so those answers are 2.
Example 2
- Input:
- [-1,5,5,-3]
- Output:
- [5,5,-1,-3]
Size 2: the window [5, 5] has minimum 5. Size 3: the windows have minimums -1 and -3, so the best is -1. Size 4 is the whole array, with minimum -3.
Example 3
- Input:
- [9]
- Output:
- [9]
There is one window, of size 1, and its minimum is 9.
Constraints
1 <= nums.length <= 40-1000 <= nums[i] <= 1000
Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.