Задача с собеседования в Josh

Задача с собеседования в 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