795. Number of Subarrays with Bounded Maximum 区间子数组个数
作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/
@TOC
题目地址:https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/description/
题目描述
We are given an array A of positive integers, and two positive integers L and R (L <= R).
Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.
Example :
Input:
A = [2, 1, 4, 3]
L = 2
R = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].
Note:
- L, R and A[i] will be an integer in the range [0, 10^9].
- The length of A will be in the range of [1, 50000].
题目大意
给定了一个数组和L,R两个数字。现在我们要求在这个数组中能有多少个连续的子数组,使得这个子数组的最大值在L和R之间。
解题方法
动态规划
第一感觉是dfs,但是看了下A的长度范围发现基本只能用O(n)的算法了,因此只能使用dp去求了。
我们设定dp数组,其dp[i]的含义是以A[i]为结尾的子数组中满足题目要求的数组个数。所以我们在这个定义的基础上,能得到下面的关系式:
- A[i] < L 这个情况,以A[i]为结尾的子数组的最大值没有改变,因此dp[i] = dp[i - 1]
- A[i] > R 此时,以A[i]为结尾的子数组的最大值已经大于了R,所以dp[i] = 0.把这个位置设定为新的开始,记录该位置为prev.
- L <= A[i] <= R 从prev到i之间的任意起始位置到i的子数组都满足题目条件,因此dp[i] = i - prev.
根据上面的关系式可以写出代码,最后的结果是整个dp之和。
该代码的时间复杂度是O(n),空间复杂度也是O(n)。
代码如下:
class Solution(object):
def numSubarrayBoundedMax(self, A, L, R):
"""
:type A: List[int]
:type L: int
:type R: int
:rtype: int
"""
if not A: return 0
dp = [0] * len(A)
prev = -1
for i, a in enumerate(A):
if a < L and i > 0:
dp[i] = dp[i - 1]
elif a > R:
dp[i] = 0
prev = i
elif L <= a <= R:
dp[i] = i - prev
return sum(dp)
因为dp[i]只和dp[i-1]有关,所以可以把空间复杂度将为O(1)。
class Solution(object):
def numSubarrayBoundedMax(self, A, L, R):
"""
:type A: List[int]
:type L: int
:type R: int
:rtype: int
"""
dp = 0
res = 0
prev = -1
for i, a in enumerate(A):
if a < L and i > 0:
res += dp
elif a > R:
dp = 0
prev = i
elif L <= a <= R:
dp = i - prev
res += dp
return res
暴力搜索+剪枝
如果二重循环可以求出每个数组,但是肯定会超时。不过,如果我们考虑一下剪枝,外层循环里面当前值大于R的时候,就移到下一个位置;内层循环里面,如果当前值大于R,那么后面的全部都不满足,所以直接break掉。这样就能过了!!
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
const int N = A.size();
int res = 0;
for (int i = 0; i < N; ++i) {
if (A[i] > R) continue;
int curMax = INT_MIN;
for (int j = i; j < N; ++j) {
curMax = max(curMax, A[j]);
if (curMax > R) break;
if (curMax >= L) ++res;
}
}
return res;
}
};
线性遍历
定一个函数count():数组中最大值小于等于bound的子数组个数。所以,我们的最终结果是就是count(R) - count(L-1)。
count函数很好设计,因为只需要线性遍历一次,就知道了。每次遍历的时候,如果当前的值小于等于bound,那么就等于在前面的子数组上又加上了一个新的数组。所以我们需要一个变量来保存前面的数组有多少个了。
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
return count(A, R) - count(A, L - 1);
}
int count(vector<int>& A, int bound) {
int res = 0, cur = 0;
for (int x : A) {
cur = (x <= bound) ? cur + 1 : 0;
res += cur;
}
return res;
}
};
我最初的想法其实就是双指针,类似虫取法。虽然想法简单,但是如果思路不够清除,根本写不出来。下面就是这个虫取法求子数组的方法。
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
const int N = A.size();
int res = 0;
int left = -1, right = -1;
for (int i = 0; i < N; ++i) {
if (A[i] > R) left = i;
if (A[i] >= L) right = i;
res += right - left;
}
return res;
}
};
参考资料: http://www.cnblogs.com/grandyang/p/9237967.html
日期
2018 年 9 月 14 日 —— 现在需要的还是夯实基础,算法和理论 2018 年 12 月 16 日 —— 周赛好难