Coverage for blog/dsa/leetcode/max_ramp_width/__init__.py: 63%

1import pytest 

2 

3 

4# start snippet monotonic_stack_push 

5def push(stack: list[int], value: int, *, _top: int | None = None) -> int: 

6 

7 top = _top or (len(stack) - 1) 

8 while stack and stack[top] > value: 

9 stack.pop() 

10 top -= 1 

11 

12 stack.append(value) 

13 

14 return top 

15 

16 # end snippet monotonic_stack_push 

17 

18 

19class SolutionFailed: 

20 def maxWidthRamp(self, nums: list[int]) -> int: 

21 

22 pairs = sorted(enumerate(nums), key=lambda pair: pair[1]) 

23 left = right = pairs[0][0] 

24 

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 

30 

31 return right - left 

32 

33 

34# start snippet solution 

35class Solution: 

36 def maxWidthRamp(self, nums: list[int]) -> int: 

37 

38 n = len(nums) 

39 stack: list[int] = [] 

40 

41 for index in range(n): 

42 num = nums[index] 

43 if not stack or nums[stack[-1]] > num: 

44 stack.append(index) 

45 

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()) 

50 

51 return max_width 

52 # end snippet solution 

53 

54 

55@pytest.fixture 

56def solution(): 

57 return Solution() 

58 

59 

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): 

71 

72 answer_computed = solution.maxWidthRamp(question) 

73 assert answer_computed == answer