Дан массив nums, имеется скользящее окно размером k, которое перемещается от самого левого края массива до самого правого. В окне можно увидеть только k чисел. Каждый раз скользящее окно перемещается вправо на одну позицию. Вернуть максимальное скользящее окно.
Пример:
Input: nums =[1,3,-1,-3,5,3,6,7]
, and k = 3 Output:[3,3,5,5,6,7] Explanation:
Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
Примечание.
Вы можете предположить, что k всегда допустимо, 1 ≤ k ≤ размера входного массива для непустого массива.
Дополнение:
Не могли бы вы решить ее за линейное время?
- Определите MyDeque с методами push(), getMax(), pop().
- Всегда убедитесь, что первый элемент является максимальным элементом.
- Используйте объект класса Element для хранения количества элементов, которые меньше или равны значению.
Запустите следующий код с приведенным выше примером, и вы поймете, как он работает.