Задача с собеседования в Josh Technology
Дан целочисленный массив nums. Ramp в массиве nums - это пара (i, j), для которой i < j и nums[i] <= nums[j]. Ширина такого ramp равна j - i.
Верните максимальную ширину ramp в nums. Если в nums нет ramp, верните 0.
Пример 1:
Input: nums = [6,0,8,2,1,5]
Output: 4
Explanation: Максимальная ширина ramp достигается при (i, j) = (1, 5): nums[1] = 0 и nums[5] = 5.
Пример 2:
Input: nums = [9,8,1,0,1,9,4,0,4,1]
Output: 7
Explanation: Максимальная ширина ramp достигается при (i, j) = (2, 9): nums[2] = 1 и nums[9] = 1.
Ограничения:
2 <= nums.length <= 5 * 10⁴
0 <= nums[i] <= 5 * 10⁴
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Необходимо найти такую пару индексов (i, j), где i < j и nums[i] <= nums[j], при этом индексы должны быть максимально удалены друг от друга.
Для решения используем монотонный стек (стек, элементы которого хранятся в строго возрастающем или строго убывающем порядке) и два прохода по массиву. В данном случае стек будет хранить индексы, упорядоченные по значениям nums[i]: значения по индексам в стеке будут образовывать строго убывающую последовательность. При добавлении нового эл-та алгоритм будет сравнивать его с вершиной стека.
В результате двух проходов:
- Первый проход (слева направо): находим кандидатов на левую границу (i).
- Второй проход (справа налево): для каждого кандидата ищем максимально удалённую правую границу (j).
Пройдем по алгоритму:
stack - стек для хранения индексов-кандидатов на левую границу (ищем максимально "низкие" значения).
Итерируемся по nums слева направо:
Если стек пуст или текущее значение меньше значения на вершине стека:
- добавляем индекс текущего эл-та в стек.
Ищем правую границу, идя от конца массива к началу, чтобы максимизировать расстояние между парами. Для каждого j проверяем, подходит ли он для левых кандидатов из стека:
Пока стек не пуст и левая граница <= правой границы (из условия: nums[i] <= nums[j]):
- вычисляем ширину пары и обновляем результат на максимально возможный.
Возвращаем res.
Сложность
O(n) - по времени (каждый индекс может быть добавлен в стек не более одного раза и удалён не более одного раза)
O(n) - по памяти (в худшем случае стек будет содержать все n индексов).
Код
class Solution:
def maxWidthRamp(self, nums: List[int]) -> int:
stack = []
res = 0
n = len(nums)
for i, num in enumerate(nums):
if not stack or nums[stack[-1]] > num:
stack.append(i)
for j in range(n)[::-1]:
while stack and nums[stack[-1]] <= nums[j]:
res = max(res, j - stack.pop())
return res
@algoses
2
2
1August 30, 2026 894 2
