Maximal Range That Each Element Is Maximum in It

To solve this problem, we can use a monotonic stack.

Create a stack stk to store elements and their positions in descending order.
Initialize two arrays left and right with the same length as nums, filled with zeros. left[i] will store the leftmost index where the subarray in which nums[i] is maximum starts, and right[i] will store the rightmost index where it ends.
Loop through the array twice: once from left to right to fill in right and once from right to left to fill in left.
Calculate the final answer ans.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from typing import List

class Solution:
    def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left = [0] * n
        right = [n - 1] * n
        stk = []

        # Step 3.1: Loop from left to right to find the rightmost boundaries
        for i, num in enumerate(nums):
            while stk and stk[-1][0] < num:
                _, idx = stk.pop()
                right[idx] = i - 1
            stk.append((num, i))

        # Clear stack for the next loop
        stk.clear()

        # Step 3.2: Loop from right to left to find the leftmost boundaries
        for i in range(n - 1, -1, -1):
            num = nums[i]
            while stk and stk[-1][0] < num:
                _, idx = stk.pop()
                left[idx] = i + 1
            stk.append((num, i))

        # Step 4: Calculate ans array based on left and right boundaries
        ans = [right[i] - left[i] + 1 for i in range(n)]

        return ans

Explanation

The stack stores elements in descending order. We use this stack to efficiently find the nearest element greater than each nums[i].
left[i] and right[i] are arrays to store the boundaries of the longest subarray where nums[i] is the maximum element.
Finally, we use these boundaries to calculate the length of each subarray.

The time complexity is (O(n)) and the space complexity is (O(n)), which are both acceptable given the constraints.