Question

2832. Maximal Range That Each Element Is Maximum in It

中文文档

Description

You are given a 0-indexed array nums of distinct integers.

Let us define a 0-indexed array ans of the same length as nums in the following way:

• ans[i] is the maximum length of a subarray nums[l..r], such that the maximum element in that subarray is equal to nums[i].

Return_ the array _ans.

Note that a subarray is a contiguous part of the array.

 

Example 1:

Input: nums = [1,5,4,3,6]
Output: [1,4,2,1,5]
Explanation: For nums[0] the longest subarray in which 1 is the maximum is nums[0..0] so ans[0] = 1.
For nums[1] the longest subarray in which 5 is the maximum is nums[0..3] so ans[1] = 4.
For nums[2] the longest subarray in which 4 is the maximum is nums[2..3] so ans[2] = 2.
For nums[3] the longest subarray in which 3 is the maximum is nums[3..3] so ans[3] = 1.
For nums[4] the longest subarray in which 6 is the maximum is nums[0..4] so ans[4] = 5.

Example 2:

Input: nums = [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: For nums[i] the longest subarray in which it's the maximum is nums[0..i] so ans[i] = i + 1.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• All elements in nums are distinct.

Solutions

Solution 1: Monotonic Stack

This problem is a template for monotonic stack. We only need to use the monotonic stack to find the position of the first element larger than $nums[i]$ on the left and right, denoted as $left[i]$ and $right[i]$. Then, the interval length with $nums[i]$ as the maximum value is $right[i] - left[i] - 1$.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array.

class Solution:
  def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:
    n = len(nums)
    left = [-1] * n
    right = [n] * n
    stk = []
    for i, x in enumerate(nums):
      while stk and nums[stk[-1]] <= x:
        stk.pop()
      if stk:
        left[i] = stk[-1]
      stk.append(i)
    stk = []
    for i in range(n - 1, -1, -1):
      while stk and nums[stk[-1]] <= nums[i]:
        stk.pop()
      if stk:
        right[i] = stk[-1]
      stk.append(i)
    return [r - l - 1 for l, r in zip(left, right)]

class Solution {
  public int[] maximumLengthOfRanges(int[] nums) {
    int n = nums.length;
    int[] left = new int[n];
    int[] right = new int[n];
    Arrays.fill(left, -1);
    Arrays.fill(right, n);
    Deque<Integer> stk = new ArrayDeque<>();
    for (int i = 0; i < n; ++i) {
      while (!stk.isEmpty() && nums[stk.peek()] <= nums[i]) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        left[i] = stk.peek();
      }
      stk.push(i);
    }
    stk.clear();
    for (int i = n - 1; i >= 0; --i) {
      while (!stk.isEmpty() && nums[stk.peek()] <= nums[i]) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        right[i] = stk.peek();
      }
      stk.push(i);
    }
    int[] ans = new int[n];
    for (int i = 0; i < n; ++i) {
      ans[i] = right[i] - left[i] - 1;
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> maximumLengthOfRanges(vector<int>& nums) {
    int n = nums.size();
    vector<int> left(n, -1);
    vector<int> right(n, n);
    stack<int> stk;
    for (int i = 0; i < n; ++i) {
      while (!stk.empty() && nums[stk.top()] <= nums[i]) {
        stk.pop();
      }
      if (!stk.empty()) {
        left[i] = stk.top();
      }
      stk.push(i);
    }
    stk = stack<int>();
    for (int i = n - 1; ~i; --i) {
      while (!stk.empty() && nums[stk.top()] <= nums[i]) {
        stk.pop();
      }
      if (!stk.empty()) {
        right[i] = stk.top();
      }
      stk.push(i);
    }
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
      ans[i] = right[i] - left[i] - 1;
    }
    return ans;
  }
};

func maximumLengthOfRanges(nums []int) []int {
  n := len(nums)
  left := make([]int, n)
  right := make([]int, n)
  for i := range left {
    left[i] = -1
    right[i] = n
  }
  stk := []int{}
  for i, x := range nums {
    for len(stk) > 0 && nums[stk[len(stk)-1]] <= x {
      stk = stk[:len(stk)-1]
    }
    if len(stk) > 0 {
      left[i] = stk[len(stk)-1]
    }
    stk = append(stk, i)
  }
  stk = []int{}
  for i := n - 1; i >= 0; i-- {
    x := nums[i]
    for len(stk) > 0 && nums[stk[len(stk)-1]] <= x {
      stk = stk[:len(stk)-1]
    }
    if len(stk) > 0 {
      right[i] = stk[len(stk)-1]
    }
    stk = append(stk, i)
  }
  ans := make([]int, n)
  for i := range ans {
    ans[i] = right[i] - left[i] - 1
  }
  return ans
}

function maximumLengthOfRanges(nums: number[]): number[] {
  const n = nums.length;
  const left: number[] = Array(n).fill(-1);
  const right: number[] = Array(n).fill(n);
  const stk: number[] = [];
  for (let i = 0; i < n; ++i) {
    while (stk.length && nums[stk.at(-1)] <= nums[i]) {
      stk.pop();
    }
    if (stk.length) {
      left[i] = stk.at(-1);
    }
    stk.push(i);
  }
  stk.length = 0;
  for (let i = n - 1; i >= 0; --i) {
    while (stk.length && nums[stk.at(-1)] <= nums[i]) {
      stk.pop();
    }
    if (stk.length) {
      right[i] = stk.at(-1);
    }
    stk.push(i);
  }
  return left.map((l, i) => right[i] - l - 1);
}