# # Leetcode 第271场周赛题解

## # Problem A - 环和杆 (opens new window)

### # 方法一：模拟

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(1)$

class Solution:
def countPoints(self, rings: str) -> int:
cnt = [set() for _ in range(10)]
for i in range(0, len(rings), 2):
id = int(rings[i + 1])
cnt[id].add(rings[i])
return len([i for i in range(10) if len(cnt[i]) == 3])

1
2
3
4
5
6
7

## # Problem B - 子数组范围和 (opens new window)

### # 方法一：暴力

• 时间复杂度$\mathcal{O}(N^2)$
• 空间复杂度$\mathcal{O}(N)$

class Solution:
def subArrayRanges(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
for i in range(n):
lo = int(1e9)
hi = -int(1e9)
for j in range(i, n):
lo = min(lo, nums[j])
hi = max(hi, nums[j])
ans += hi - lo

return ans

1
2
3
4
5
6
7
8
9
10
11
12
13

### # 方法二：单调栈

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(N)$

class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
int n = nums.size();
long long ans = 0;

vector<int> l(n, -1), r(n, n);
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && nums[i] >= nums[st.top()]) {
r[st.top()] = i;
st.pop();
}
st.push(i);
}

st = stack<int>();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && nums[i] > nums[st.top()]) {
l[st.top()] = i;
st.pop();
}
st.push(i);
}

for (int i = 0; i < n; ++i)
ans += 1LL * nums[i] * (i - l[i]) * (r[i] - i);

l.assign(n, -1), r.assign(n, n);
st = stack<int>();
for (int i = 0; i < n; ++i) {
while (!st.empty() && nums[i] <= nums[st.top()]) {
r[st.top()] = i;
st.pop();
}
st.push(i);
}

st = stack<int>();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && nums[i] < nums[st.top()]) {
l[st.top()] = i;
st.pop();
}
st.push(i);
}

for (int i = 0; i < n; ++i)
ans -= 1LL * nums[i] * (i - l[i]) * (r[i] - i);

return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

## # Problem C - 给植物浇水 II (opens new window)

### # 方法一：模拟

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(1)$

class Solution {
public:
int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {
int n = plants.size();
int a = capacityA, b = capacityB;
int l = 0, r = n - 1;
int ans = 0;

while (l <= r) {
int lastA = a;
if (l < r || a >= b) {
if (a >= plants[l]) {
a -= plants[l];
} else {
a = capacityA - plants[l];
ans++;
}
}

if (l < r || lastA < b) {
if (b >= plants[r]) {
b -= plants[r];
} else {
b = capacityB - plants[r];
ans++;
}
}

l++, r--;
}

return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

## # Problem D - 摘水果 (opens new window)

### # 方法一：双指针

• 先往左，如果还有步数，再往右
• 先往右，如果还有步数，再往左

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(1)$

const int INF = 1e9;

class Solution {
int solve(vector<vector<int>>& fruits, int startPos, int k) {
int n = fruits.size();
int p = upper_bound(fruits.begin(), fruits.end(), vector<int>{startPos, INF}) - fruits.begin() - 1;
int ans = 0, r = 0, sum = 0;
for (int i = 0; i <= p; ++i)
sum += fruits[i][1];

for (int l = 0; l <= p; ++l) {
if (l >= 1)
sum -= fruits[l - 1][1];
if (startPos - fruits[l][0] > k)
continue;
r = max(r, l);
while (r + 1 < n && startPos - fruits[l][0] + fruits[r + 1][0] - fruits[l][0] <= k) {
r++;
if (r > p)
sum += fruits[r][1];
}
ans = max(ans, sum);
}

return ans;
}
public:
int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
int ans = solve(fruits, startPos, k);

for (auto &fruit : fruits)
fruit[0] = -fruit[0];
reverse(fruits.begin(), fruits.end());
ans = max(ans, solve(fruits, -startPos, k));

return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38