class Solution {
public:
int validSubarrays(vector<int>& nums) {
}
};
1063. 有效子数组的数目
给定一个整数数组 nums ，返回满足下面条件的 非空、连续 子数组的数目：
示例 1：
输入：nums = [1,4,2,5,3] 输出：11 解释：有 11 个有效子数组，分别是：[1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3] 。
示例 2：
输入：nums = [3,2,1] 输出：3 解释：有 3 个有效子数组，分别是：[3],[2],[1] 。
示例 3：
输入：nums = [2,2,2] 输出：6 解释：有 6 个有效子数组，分别为是：[2],[2],[2],[2,2],[2,2],[2,2,2] 。
提示：
1 <= nums.length <= 5 * 1040 <= nums[i] <= 105原站题解
golang 解法, 执行用时: 48 ms, 内存消耗: 7 MB, 提交时间: 2023-10-17 12:05:54
func validSubarrays(nums []int) (ans int) {
type pair struct{ v, i int }
stk := []pair{{-1, len(nums)}}
for i := len(nums) - 1; i >= 0; i-- {
for stk[len(stk)-1].v >= nums[i] {
stk = stk[:len(stk)-1]
}
ans += stk[len(stk)-1].i - i
stk = append(stk, pair{nums[i], i})
}
return
}
java 解法, 执行用时: 6 ms, 内存消耗: 51.4 MB, 提交时间: 2023-10-17 12:05:22
class Solution {
public int validSubarrays1(int[] nums) {
// 单调栈的操作
Stack<Integer> stack = new Stack<>();
int ans = 0;
for(int i = 0;i<nums.length;i++) {
while(!stack.isEmpty()&&nums[stack.peek()]>nums[i]) {
ans += (i-stack.peek());
stack.pop();
}
stack.push(i);
}
while(!stack.isEmpty()) {
ans += nums.length-stack.pop();
}
return ans;
}
// dp
public int validSubarrays(int[] nums) {
if (nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return 1;
}
int sum = nums.length;
int[] dpTable = new int[nums.length];
Arrays.fill(dpTable, 0);
for (int i = nums.length - 2; i >= 0; i--) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] <= nums[j]) {
//这一步是优化点：可以少遍历一些
if (dpTable[j] != 0) {
j = dpTable[j];
}
dpTable[i] = j;
} else {
break;
}
}
if (dpTable[i] != 0) {
int count = dpTable[i] - i;
// System.out.println(count);
sum += count;
}
}
return sum;
}
}
python3 解法, 执行用时: 132 ms, 内存消耗: 20.9 MB, 提交时间: 2023-10-17 12:03:32
class Solution:
def validSubarrays1(self, nums: List[int]) -> int:
nums = nums + [-1] # 哨兵。防止12345不计算
n = len(nums)
res = 0
inc_stk = [] #哨兵
for i in range(n):
while inc_stk and nums[inc_stk[-1]] > nums[i]: #单调递增栈，右侧第一个小于当前元素的index
res += i - inc_stk.pop(-1)
inc_stk.append(i)
return res
def validSubarrays2(self, nums: List[int]) -> int:
n = len(nums)
res = 0
#------------- 单调递增栈，不使用哨兵 ----------------#
inc_stk = []
for i in range(n):
while inc_stk and nums[inc_stk[-1]] > nums[i]:
res += i - inc_stk.pop(-1)
inc_stk.append(i)
while inc_stk:
res += n - inc_stk.pop(-1)
return res
def validSubarrays3(self, nums: List[int]) -> int:
n = len(nums)
inc_stk = []
res = 0
for x in nums:
while inc_stk and inc_stk[-1] > x:
inc_stk.pop(-1)
inc_stk.append(x)
res += len(inc_stk) #以x为右端的情况
return res
def validSubarrays(self, nums: List[int]) -> int:
n = len(nums)
res = 0
#------------- 单调递增栈，不使用哨兵 ----------------#
R_first_less = [n for _ in range(n)] #右侧第一个小于当前位置的
inc_stk = []
for i in range(n):
while inc_stk and nums[inc_stk[-1]] > nums[i]:
R_first_less[inc_stk.pop(-1)] = i
inc_stk.append(i)
res = 0
for i in range(n):
res += R_first_less[i] - i
return res
cpp 解法, 执行用时: 52 ms, 内存消耗: 43.7 MB, 提交时间: 2023-10-17 12:02:15
class Solution {
public:
int validSubarrays(vector<int>& nums) {
if (nums.size() < 2) return nums.size();
int res = 0;
stack<int> st;
int N = nums.size();
for (int i = 0; i < N; ++i) {
while (!st.empty() && nums[st.top()] > nums[i]) {
res += i - st.top();
st.pop();
}
st.push(i);
}
while (!st.empty()) {
res += N - st.top();
st.pop();
}
return res;
}
};