Question

1063. Number of Valid Subarrays

中文文档

Description

Given an integer array nums, return _the number of non-empty subarrays with the leftmost element of the subarray not larger than other elements in the subarray_.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

Example 2:

Input: nums = [3,2,1]
Output: 3
Explanation: The 3 valid subarrays are: [3],[2],[1].

Example 3:

Input: nums = [2,2,2]
Output: 6
Explanation: There are 6 valid subarrays: [2],[2],[2],[2,2],[2,2],[2,2,2].

 

Constraints:

• 1 <= nums.length <= 5 * 104
• 0 <= nums[i] <= 105

Solutions

Solution 1

class Solution:
  def validSubarrays(self, nums: List[int]) -> int:
    n = len(nums)
    right = [n] * n
    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 sum(j - i for i, j in enumerate(right))

class Solution {
  public int validSubarrays(int[] nums) {
    int n = nums.length;
    int[] right = new int[n];
    Arrays.fill(right, n);
    Deque<Integer> stk = new ArrayDeque<>();
    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 = 0;
    for (int i = 0; i < n; ++i) {
      ans += right[i] - i;
    }
    return ans;
  }
}

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

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

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

Solution 2

class Solution:
  def validSubarrays(self, nums: List[int]) -> int:
    n = len(nums)
    stk = []
    ans = 0
    for i in range(n - 1, -1, -1):
      while stk and nums[stk[-1]] >= nums[i]:
        stk.pop()
      ans += (stk[-1] if stk else n) - i
      stk.append(i)
    return ans

class Solution {
  public int validSubarrays(int[] nums) {
    int n = nums.length;
    Deque<Integer> stk = new ArrayDeque<>();
    int ans = 0;
    for (int i = n - 1; i >= 0; --i) {
      while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) {
        stk.pop();
      }
      ans += (stk.isEmpty() ? n : stk.peek()) - i;

      stk.push(i);
    }
    return ans;
  }
}

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

func validSubarrays(nums []int) (ans int) {
  n := len(nums)
  stk := []int{}
  for i := n - 1; i >= 0; i-- {
    for len(stk) > 0 && nums[stk[len(stk)-1]] >= nums[i] {
      stk = stk[:len(stk)-1]
    }
    ans -= i
    if len(stk) > 0 {
      ans += stk[len(stk)-1]
    } else {
      ans += n
    }
    stk = append(stk, i)
  }
  return
}

function validSubarrays(nums: number[]): number {
  const n = nums.length;
  const stk: number[] = [];
  let ans = 0;
  for (let i = n - 1; ~i; --i) {
    while (stk.length && nums[stk.at(-1)!] >= nums[i]) {
      stk.pop();
    }
    ans += (stk.at(-1) ?? n) - i;
    stk.push(i);
  }
  return ans;
}