Skip to content

2832. Maximal Range That Each Element Is Maximum in It 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  vector<int> maximumLengthOfRanges(vector<int>& nums) {
    vector<int> ans(nums.size());
    stack<int> stack;  // a decreasing stack

    for (int i = 0; i <= nums.size(); ++i) {
      while (!stack.empty() &&
             (i == nums.size() || nums[stack.top()] < nums[i])) {
        const int index = stack.top();
        stack.pop();
        const int left = stack.empty() ? -1 : stack.top();
        ans[index] = i - left - 1;
      }
      stack.push(i);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int[] maximumLengthOfRanges(int[] nums) {
    int[] ans = new int[nums.length];
    Deque<Integer> stack = new ArrayDeque<>(); // a decreasing stack

    for (int i = 0; i <= nums.length; ++i) {
      while (!stack.isEmpty() && (i == nums.length || nums[stack.peek()] < nums[i])) {
        final int index = stack.pop();
        final int left = stack.isEmpty() ? -1 : stack.peek();
        ans[index] = i - left - 1;
      }
      stack.push(i);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:
    ans = [0] * len(nums)
    stack = []  # a decreasing stack

    for i in range(len(nums) + 1):
      while stack and (i == len(nums) or nums[stack[-1]] < nums[i]):
        index = stack.pop()
        left = stack[-1] if stack else -1
        ans[index] = i - left - 1
      stack.append(i)

    return ans