子数组，你让我拿什么爱你？
周赛的时候被第二题卡了一下，自己之前做过子数组的问题，可以用单调栈优化，比赛的时候也往这方面想了
思维有点难度，老是有 bug，突然发现过了一千多人，这才感觉到不对劲，这才发现数据范围看错了，遂改为暴力，又要掉分了，死在子数组上...
涉及知识点：模拟、子数组、单调栈、双指针、前缀和、二分查找、离散化
5952. 环和杆
给定一个字符串形如 R3G2B1，表示杆子 3, 2, 1 上分别有 R, G, B 颜色的圈
解析这个字符串，返回杆子上集齐了 rgb 三种颜色的杆子数量
题解
直接按字符解析，用哈希表套集合处理即可
// cpp
class Solution {
public:
int countPoints(string r) {
unordered_map<int, set<int>> mp;
for (int i = 0; i < r.size() - 1; i += 2) {
int j = i + 1;
if (!mp[r[j] - '0'].count(r[i])) mp[r[j] - '0'].insert(r[i]);
}
int ans = 0;
for (auto& i: mp) {
if (i.second.size() == 3) ans++;
}
return ans;
}
};
5953. 子数组范围和
给定一个长度为 n 的数组，返回所有子数组最大值与最小值差的和数据规定1\leq n\leq 10^3
题解
这题比赛的时候想复杂了，直接爆炸数据范围不高，直接考虑 \mathcal{O}(n^2) 的做法
可以固定左端点，枚举右端点，然后维护最大最小值即可
// cpp
class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
typedef long long LL;
int n = nums.size();
LL ans = 0;
for (int i = 0; i < n; ++i) {
LL maxx = nums[i], minn = nums[i];
for (int j = i + 1; j < n; ++j) {
maxx = max(maxx, 1LL * nums[j]);
minn = min(minn, 1LL * nums[j]);
ans += maxx - minn;
}
}
return ans;
}
};
如果数据范围放大到 1\leq n\leq 10^5 ，需要考虑 \mathcal{O}(n) 的做法
我们需要计算出每个元素 nums[i] 作为最大值、最小值所管辖的区间
以最大值为例，我们定义 dp[i] 表示到 i 为止最大值的和，我们需要用单调栈找到 i 左边第一个大于 nums[i] 的位置 j，然后可以状态转移方程 dp[i] = (j - i) * nums[i] + dp[j]，最小值同理
// cpp
class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
typedef long long LL;
int n = nums.size();
vector<LL> maxx(n + 1), minn(n + 1);
vector<int> lse(n + 1, 0), lge(n + 1, 0);
stack<int> stk;
for (int i = n; i >= 1; --i) {
while (!stk.empty() && nums[stk.top() - 1] < nums[i - 1]) {
lge[stk.top()] = i;
stk.pop();
}
stk.push(i);
}
while (!stk.empty()) stk.pop();
for (int i = n; i >= 1; --i) {
while (!stk.empty() && nums[stk.top() - 1] > nums[i - 1]) {
lse[stk.top()] = i;
stk.pop();
}
stk.push(i);
}
LL ans = 0;
for (int i = 1; i <= n; ++i) {
//cout << i << ' ' << lge[i] << ' ' << lse[i] << endl;
int j = lge[i];
maxx[i] = 1LL * (i - j) * nums[i - 1] + maxx[j];
j = lse[i];
minn[i] = 1LL * (i - j) * nums[i - 1] + minn[j];
ans += maxx[i] - minn[i];
}
return ans;
}
};
5954. 给植物浇水 II
数轴上分布了 n 个植物，A,\ B 从两头开始给植物浇水，每个人水桶的容量分别为CA,\ CB
如果植物所需要的水量超过当前水桶的量，他们需要补水，计算浇灌结束所有植物的时候，他们补水的次数
数据规定1\leq n\leq 10^5
题解
两个指针从数组两头扫描，模拟浇灌的过程，时间复杂度\mathcal{O}(n)
// cpp
class Solution {
public:
int minimumRefill(vector<int>& p, int ca, int cb) {
int n = p.size();
int i = 0, j = n - 1, a = ca, b = cb, ans = 0;
while (i <= j) {
if (i == j) {
if (a == b) {
if (a < p[i]) a = ca, ans++;
a -= p[i++];
}
else if (a < b) {
if (b < p[j]) b = cb, ans++;
b -= p[j--];
}
else {
if (a < p[i]) a = ca, ans++;
a -= p[i++];
}
}
else {
if (a < p[i]) ans++, a = ca;
a -= p[i++];
if (b < p[j]) ans++, b = cb;
b -= p[j--];
}
}
return ans;
}
};
5955. 摘水果
给定一个坐标轴，上面分布了 n 个水果，每个水果有自己的坐标 p_{i} 和价值f_{i} 你位于 st ，每次移动一单位耗费一点体力值，你一共有 k 体力，计算可以获得的最大水果价值数据规定1\leq n\leq 10^5,\ 1\leq p_{i},\ st,\ k\leq 2\cdot 10^5,\ 1\leq f_{i}\leq 10^4
题解
考虑从 st 出发，向右走 x ，那么向左走 y = \frac{(k - x)}{2} ，轨迹为 [st - y, st + x] ，我们只要计算该区间的最大价值即可考虑从 st 出发，向左走 x ，那么向右走 y = \frac{(k - x)}{2} ，轨迹为 [st - x, st + y] ，我们只要计算该区间的最大价值即可预处理前缀和，在数轴不那么大的情况下，我们可以直接计算整个数轴的前缀和，时间复杂度\mathcal{{O}(k)}
// cpp
class Solution {
public:
int maxTotalFruits(vector<vector<int>>& f, int st, int k) {
int n = f.size();
int max_r = (*(max_element(f.begin(), f.end(), [&](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
})))[0] + 1;
//cout << max_r << endl;
vector<int> sum(max_r + 1);
for (int i = 0; i < n; ++i) {
sum[f[i][0] + 1] += f[i][1];
}
for (int i = 1; i <= max_r; ++i) {
sum[i] += sum[i - 1];
}
st++;
int ans = 0;
for (int x = k; x >= 0; --x) {
int y = (k - x) / 2;
int L1 = max(1, st - y), R1 = min(max_r, st + x);
int L2 = max(1, st - x), R2 = min(max_r, st + y);
if (L1 > R1 && L2 > R2) continue;
if (L1 <= R1) ans = max(ans, sum[R1] - sum[L1 - 1]);
if (L2 <= R2) ans = max(ans, sum[R2] - sum[L2 - 1]);
}
return ans;
}
};
如果数轴特别大，需要离散化记录前缀和，否则时间和空间都会爆炸，时间复杂度为\mathcal{O}(k\cdot \log n)
// cpp
class Solution {
public:
int maxTotalFruits(vector<vector<int>>& f, int st, int k) {
int n = f.size();
vector<int> sum;
sum.push_back(0);
for (int i = 1; i <= n; ++i) {
sum.push_back(f[i - 1][1] + sum[i - 1]);
}
vector<int> pos;
for (auto& i: f) pos.push_back(i[0]);
int ans = 0;
for (int x = k; x >= 0; --x) {
int y = (k - x) / 2;
int L = st - y, R = st + x;
auto l = lower_bound(pos.begin(), pos.end(), L) - pos.begin();
auto r = upper_bound(pos.begin(), pos.end(), R) - pos.begin();
ans = max(ans, sum[r] - sum[l]);
L = st - x, R = st + y;
l = lower_bound(pos.begin(), pos.end(), L) - pos.begin();
r = upper_bound(pos.begin(), pos.end(), R) - pos.begin();
ans = max(ans, sum[r] - sum[l]);
}
return ans;
}
};
腾讯云开发者
