Given an array arr of n integers, find the number of its subarrays such that removing the subarray creates a non-empty array that is sorted in increasing order.
Note: A subarray is defined as any contiguous segment of the array.
Constraints
1 ≤ n ≤ 2×10⁵1 ≤ arr[i] ≤ 10⁹
Example 1
Input:
arr = [1, 2, 1, 2]Output:
7Explanation:
There are 7 subarrays that on removal produce a non-empty sorted array. Hence, the answer is 7.
The subarrays [3], [3, 1] and [1, 2] give a non-empty sorted array on removal.
Example 2
Input:
arr = [3, 1, 2]Output:
3Explanation:
The subarrays [3], [3, 1] and [1, 2] give a non-empty sorted array on removal.
Example 3
Input:
arr = [1, 2, 2, 6, 1, 3]Output:
10Explanation:
The subarrays [1, 2, 2, 6], [1, 2, 2, 6, 1], [2, 2, 6], [2, 2, 6, 1], [2, 6], [2, 6, 1], [6], [6, 1], [1, 3] and [1] give a non-empty sorted array on removal.
解法
先求最长严格递增的前缀长度 L(arr[0..L-1])，后缀长度 R(arr[n-R..n-1])。枚举保留的左前缀长度 i(从 0 到 L)，用双指针在右后缀里找最小 j 使 arr[n-1-j] > arr[i-1](i=0 时无下界)。答案 = Σ (R - j + 1)，需去掉空子数组并保证移除非空。O(n)。
from typing import List
def countRemovableSubarrays(arr: List[int]) -> int:
n = len(arr)
# 找最长严格递增前缀长度 L
L = 1
while L < n and arr[L] > arr[L - 1]:
L += 1
if L == n:
# 整体已严格递增，任意非空子数组都满足
return n * (n + 1) // 2
# 找最长严格递增后缀长度 R
R = 1
while R < n and arr[n - R - 1] < arr[n - R]:
R += 1
# 双指针：保留左 i 个 + 保留右 j 个，要求 arr[i-1] < arr[n-j]
ans = 0
j = R
for i in range(L + 1):
while j > 0 and (i > 0 and arr[n - j] <= arr[i - 1]):
j -= 1
# 移除子数组 = arr[i..n-j-1]，长度 = n - j - i，必须非空 → j + i < n
if i + j < n:
ans += 1 # 这个唯一切分对应 1 个子数组
else:
# 切分使得"移除"是空，跳过
pass
# 上面的方法只数了 (i, j) 对应的 (start=i, end=n-j-1) 子数组数；但题目允许扩张
# 实际：对每个左保留长度 i，合法的 j 范围 [j_min(i), R]，每个 j 对应一个子数组
# 重新写：
ans = 0
j_ptr = R
for i in range(L + 1):
# 找最大的 j 使 arr[n-j] > arr[i-1] (i==0 时任何 j 都行)
while j_ptr > 0 and i > 0 and arr[n - j_ptr] <= arr[i - 1]:
j_ptr -= 1
max_j = j_ptr
# j 可以从 0 到 max_j；要求移除非空：i + j < n
upper = min(max_j, n - i - 1)
if upper >= 0:
ans += upper + 1
return ansclass Solution {
long countRemovableSubarrays(int[] arr) {
int n = arr.length;
int L = 1;
while (L < n && arr[L] > arr[L - 1]) L++;
if (L == n) return (long) n * (n + 1) / 2;
int R = 1;
while (R < n && arr[n - R - 1] < arr[n - R]) R++;
long ans = 0;
int jPtr = R;
for (int i = 0; i <= L; i++) {
while (jPtr > 0 && i > 0 && arr[n - jPtr] <= arr[i - 1]) jPtr--;
int maxJ = jPtr;
int upper = Math.min(maxJ, n - i - 1);
if (upper >= 0) ans += upper + 1;
}
return ans;
}
}class Solution {
public:
long long countRemovableSubarrays(vector<int>& arr) {
int n = arr.size();
int L = 1;
while (L < n && arr[L] > arr[L - 1]) L++;
if (L == n) return (long long) n * (n + 1) / 2;
int R = 1;
while (R < n && arr[n - R - 1] < arr[n - R]) R++;
long long ans = 0;
int jPtr = R;
for (int i = 0; i <= L; i++) {
while (jPtr > 0 && i > 0 && arr[n - jPtr] <= arr[i - 1]) jPtr--;
int maxJ = jPtr;
int upper = min(maxJ, n - i - 1);
if (upper >= 0) ans += upper + 1;
}
return ans;
}
};There is a straight line of students of various heights. The students' heights are given in the form of an array, in the order they are standing in the line.
Consider the region of a student as the length of the largest subarray that includes that student's position, and in which that student's height is equal to maximum height among all students present in that subarray. Return the sum of the region of all students.
Function Description
Complete the function calculateTotalRegion in the editor.
calculateTotalRegion has the following parameter(s):
heights: an array of the heights of students standing in the line Returnslong integer: the desired sum of all regions
Constraints
- 1 ≤ length of heights ≤ 10⁵
- 1 ≤ heights[i] ≤ 10⁹
Example 1
Input:
heights = [3, 5, 6]Output:
6Explanation: The longest subarray in which the first student's height is equal to the maximum height among all other students is [3]; thus, the length of the region of the first student is 1. The longest subarray in which the second student's height is equal to maximum height among all other students is [3, 5]; thus, the length of the region of the second student is 2. The longest subarray in which the third student's height is equal to the maximum height among all other students is [3, 5, 6]; thus, the length of the region of the third student is 3. Thus, the sum of the lengths of all regions of all students is 1 + 2 + 3 = 6.
Example 2
Input:
heights = [1, 2, 1]Output:
5Explanation: Subarrays for values 1, 2, and 1 are [1], [1, 2], and [1]. The sum of their lengths is 1 + 3 + 1 = 5.
解法
单调栈：对每个 i 求其作为最大值时左右能延伸到的最远边界 left[i], right[i]，region 长度 = right[i] - left[i] + 1。累加。O(n)。
from typing import List
def calculateTotalRegion(heights: List[int]) -> int:
n = len(heights)
left = [0] * n # 最远左下标 (>= 0)
right = [n - 1] * n
stack = []
for i in range(n):
# 严格大才弹出，相等的也归入同一组（避免重复，使用 ≥ / >）
while stack and heights[stack[-1]] < heights[i]:
stack.pop()
left[i] = stack[-1] + 1 if stack else 0
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] <= heights[i]:
stack.pop()
right[i] = stack[-1] - 1 if stack else n - 1
stack.append(i)
return sum(right[i] - left[i] + 1 for i in range(n))import java.util.*;
class Solution {
long calculateTotalRegion(int[] heights) {
int n = heights.length;
int[] left = new int[n], right = new int[n];
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && heights[st.peek()] < heights[i]) st.pop();
left[i] = st.isEmpty() ? 0 : st.peek() + 1;
st.push(i);
}
st.clear();
for (int i = n - 1; i >= 0; i--) {
while (!st.isEmpty() && heights[st.peek()] <= heights[i]) st.pop();
right[i] = st.isEmpty() ? n - 1 : st.peek() - 1;
st.push(i);
}
long ans = 0;
for (int i = 0; i < n; i++) ans += right[i] - left[i] + 1;
return ans;
}
}class Solution {
public:
long long calculateTotalRegion(vector<int>& heights) {
int n = heights.size();
vector<int> left(n), right(n);
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && heights[st.top()] < heights[i]) st.pop();
left[i] = st.empty() ? 0 : st.top() + 1;
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && heights[st.top()] <= heights[i]) st.pop();
right[i] = st.empty() ? n - 1 : st.top() - 1;
st.push(i);
}
long long ans = 0;
for (int i = 0; i < n; i++) ans += right[i] - left[i] + 1;
return ans;
}
};You are given a 0-indexed array of positive integers nums.
A subarray of nums is called incremovable if nums becomes strictly increasing on removing the subarray. For example, the subarray [3, 4] is an incremovable subarray of [5, 3, 4, 6, 7] because removing this subarray changes the array [5, 3, 4, 6, 7] to [5, 6, 7], which is strictly increasing.
Return the total number of incremovable subarrays of nums.
Note that an empty array is considered strictly increasing.
A subarray is a contiguous non-empty sequence of elements within an array.
Constraints
- `1
Example 1
Input:
nums = [1,2,3,4]Output:
10Explanation:
The 10 incremovable subarrays are: [1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4], and [1,2,3,4], because on removing any one of these subarrays nums becomes strictly increasing. Note that you cannot select an empty subarray.
Example 2
Input:
nums = [6,5,7,8]Output:
7Explanation:
The 7 incremovable subarrays are: [5], [6], [5,7], [6,5], [5,7,8], [6,5,7], and [6,5,7,8].
It can be shown that there are only 7 incremovable subarrays in nums.
Example 3
Input:
nums = [8,7,6,6]Output:
3Explanation:
The 3 incremovable subarrays are: [8,7,6], [7,6,6], and [8,7,6,6]. Note that [8,7] is not an incremovable subarray because after removing [8,7] nums becomes [6,6], which is sorted in ascending order but not strictly increasing.
解法
同 LC 2972：先求最长严格递增前缀 L 与后缀 R。若整体已严格递增，答案 n*(n+1)/2。否则枚举保留的左长度 i(0..L)，双指针找最大 j 使 nums[n-j] > nums[i-1]，累加 j + 1(去除前缀+后缀的所有"中间删除"方案)。O(n)。
from typing import List
def incremovableSubarrayCount(nums: List[int]) -> int:
n = len(nums)
L = 1
while L < n and nums[L] > nums[L - 1]:
L += 1
if L == n:
return n * (n + 1) // 2
# 最长严格递增后缀
R = 1
while R < n and nums[n - R - 1] < nums[n - R]:
R += 1
ans = R + 1 # i = 0 时，j ∈ [0..R]
# 双指针
j_ptr = R
for i in range(1, L + 1):
while j_ptr > 0 and nums[n - j_ptr] <= nums[i - 1]:
j_ptr -= 1
max_j = j_ptr
upper = min(max_j, n - i - 1) # 移除非空
if upper >= 0:
ans += upper + 1
return ansclass Solution {
long incremovableSubarrayCount(int[] nums) {
int n = nums.length;
int L = 1;
while (L < n && nums[L] > nums[L - 1]) L++;
if (L == n) return (long) n * (n + 1) / 2;
int R = 1;
while (R < n && nums[n - R - 1] < nums[n - R]) R++;
long ans = R + 1;
int jPtr = R;
for (int i = 1; i <= L; i++) {
while (jPtr > 0 && nums[n - jPtr] <= nums[i - 1]) jPtr--;
int maxJ = jPtr;
int upper = Math.min(maxJ, n - i - 1);
if (upper >= 0) ans += upper + 1;
}
return ans;
}
}class Solution {
public:
long long incremovableSubarrayCount(vector<int>& nums) {
int n = nums.size();
int L = 1;
while (L < n && nums[L] > nums[L - 1]) L++;
if (L == n) return (long long) n * (n + 1) / 2;
int R = 1;
while (R < n && nums[n - R - 1] < nums[n - R]) R++;
long long ans = R + 1;
int jPtr = R;
for (int i = 1; i <= L; i++) {
while (jPtr > 0 && nums[n - jPtr] <= nums[i - 1]) jPtr--;
int maxJ = jPtr;
int upper = min(maxJ, n - i - 1);
if (upper >= 0) ans += upper + 1;
}
return ans;
}
};