I was stuck by the second question in the week competition. I had done the problem of sub array before. I can use monotone stack optimization. I also thought about this aspect during the competition
It's a little difficult to think. There are always bug s. I suddenly found more than 1000 people. Then I felt something wrong. I found that the data range was wrong, so I changed it to violence, lost points and died on the sub array
Knowledge points involved: simulation, subarray, monotone stack, double pointer, prefix sum, binary search, discretization
5952. Ring and rod
Given a string shape such as R3G2B1, it means that there are R, G and B circles on rods 3, 2 and 1 respectively
Parse this string and return the number of rods with rgb three colors on the rod
Problem solution
It can be parsed directly by characters and processed by hash table set
// 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. Subarray range and
Given an array of length N, return the sum of the difference between the maximum and minimum values of all subarrays. 1\leq n\leq 10^3
Problem solution
The problem was complicated during the competition. The range of direct explosion data was not high. The practice of \ mathcal{O}(n^2) was directly considered
You can fix the left endpoint, enumerate the right endpoint, and then maintain the maximum and minimum values
// 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;
}
};
If the data range is enlarged to 1\leq n\leq 10^5, the approach of \ mathcal{O}(n) needs to be considered
We need to calculate the interval governed by each element num [i] as the maximum and minimum values
Taking the maximum value as an example, we define dp[i] to represent the sum of the maximum value up to I. We need to use the monotone stack to find the first position j on the left of I that is greater than num [i], and then we can use the state transition equation dp[i] = (j - I) * num [i] + DP [j], which is the same as the minimum value
// 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. Watering plants II
n plants are distributed on the number axis. A and \ B water the plants from both ends. The capacity of each person's bucket is Ca and \ CB respectively
If the plants need more water than the current bucket, they need to replenish water. Calculate the number of times they replenish water when watering all plants is over
Data specification 1\leq n\leq 10^5
Problem solution
Two pointers are scanned from both ends of the array to simulate the pouring process. The time complexity is \ 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. Picking fruit
Given a coordinate axis, n fruits are distributed on it, and each fruit has its own coordinate p_{i} And value f_{i} You are located in St, and each time you move a unit, it costs a little physical strength. You have K physical strength in total. Calculate the maximum fruit value data that can be obtained. Specify 1\leq n\leq 10^5,\ 1\leq p_{i},\ st,\ k\leq 2\cdot 10^5,\ 1\leq f_{i}\leq 10^4
Problem solution
Consider starting from St and going right x, then going left y = \frac{(k - x)}{2}, and the trajectory is [st - y, st + x]. We can consider starting from St and going left x, then going right y = \frac{(k - x)}{2}, and the trajectory is [st - x, st + y]. We can preprocess the prefix sum as long as we calculate the maximum value of the interval, When the number axis is not so large, we can directly calculate the prefix and time complexity of the whole number axis \ 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;
}
};
If the number axis is very large, you need to discretize the record prefix and, otherwise time and space will explode. The time complexity is \ 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;
}
};