Coverage for blog/dsa/leetcode/max_ramp_width/__init__.py: 63%
38 statements
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
1import pytest
4# start snippet monotonic_stack_push
5def push(stack: list[int], value: int, *, _top: int | None = None) -> int:
7 top = _top or (len(stack) - 1)
8 while stack and stack[top] > value:
9 stack.pop()
10 top -= 1
12 stack.append(value)
14 return top
16 # end snippet monotonic_stack_push
19class SolutionFailed:
20 def maxWidthRamp(self, nums: list[int]) -> int:
22 pairs = sorted(enumerate(nums), key=lambda pair: pair[1])
23 left = right = pairs[0][0]
25 for index, _ in pairs:
26 if index < left and nums[index] <= nums[right]:
27 left = index
28 elif right < index and nums[left] <= nums[index]:
29 right = index
31 return right - left
34# start snippet solution
35class Solution:
36 def maxWidthRamp(self, nums: list[int]) -> int:
38 n = len(nums)
39 stack: list[int] = []
41 for index in range(n):
42 num = nums[index]
43 if not stack or nums[stack[-1]] > num:
44 stack.append(index)
46 max_width = 0
47 for k in range(n - 1, -1, -1):
48 while stack and nums[stack[-1]] <= nums[k]:
49 max_width = max(max_width, k - stack.pop())
51 return max_width
52 # end snippet solution
55@pytest.fixture
56def solution():
57 return Solution()
60@pytest.mark.parametrize(
61 "question, answer",
62 (
63 ([6, 0, 8, 2, 1, 5], 4),
64 ([9, 8, 1, 0, 1, 9, 4, 0, 4, 1], 7),
65 ([2, 1, 3], 2),
66 ([2, 2, 1], 1),
67 ([2, 4, 1, 3], 3),
68 ),
69)
70def test_solution(solution: Solution, question: list[int], answer: int):
72 answer_computed = solution.maxWidthRamp(question)
73 assert answer_computed == answer