# # Leetcode 第217场周赛题解

## # Problem A - 最富有客户的资产总量 (opens new window)

class Solution:
def maximumWealth(self, accounts: List[List[int]]) -> int:
return max([sum(l) for l in accounts])

1
2
3

## # Problem B - 找出最具竞争力的子序列 (opens new window)

### # 方法一 稀疏表

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

class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
int n = nums.size();
int d = int(log2(n));
vector<vector<int>> lo(n, vector<int>(d + 1));
for (int i = 0; i < n; ++i)
lo[i][0] = i;
for (int k = 1; k <= d; ++k)
for (int i = 0; i < n; ++i) {
lo[i][k] = lo[i][k - 1];
int r = i + (1 << (k - 1));
if (r < n && nums[lo[r][k - 1]] < nums[lo[i][k]])
lo[i][k] = lo[r][k - 1];
}
auto query = [&](int l, int r) {
int k = log2(r - l + 1);
int L = lo[l][k], R = lo[r - (1 << k) + 1][k];
if (nums[L] <= nums[R])
return L;
return R;
};
vector<int> ans;
int L = 0, m = 0;
while (m < k) {
int idx = query(L, n - k + m);
ans.emplace_back(nums[idx]);
L = idx + 1;
m++;
}
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

### # 方法二 优先队列

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

class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
int n = nums.size();
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
for (int i = 0; i < n - k + 1; ++i)
pq.emplace(nums[i], i);
vector<int> ans;
int l = 0;
for (int i = 0; i < k; ++i) {
while (pq.top().second < l)
pq.pop();
auto [num, idx] = pq.top();
pq.pop();
l = idx + 1;
ans.emplace_back(num);
if (i < k - 1)
pq.emplace(nums[n - k + i + 1], n - k + i + 1);
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

### # 方法三 单调队列

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

class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
int n = nums.size();
deque<int> dq;
for (int i = 0; i < n - k + 1; ++i) {
while (!dq.empty() && nums[dq.back()] > nums[i])
dq.pop_back();
dq.push_back(i);
}
vector<int> ans;
int l = 0;
for (int i = 0; i < k; ++i) {
while (dq.front() < l)
dq.pop_front();
int idx = dq.front();
int num = nums[idx];
dq.pop_front();
l = idx + 1;
ans.emplace_back(num);
if (i < k - 1) {
while (!dq.empty() && nums[dq.back()] > nums[n - k + 1 + i])
dq.pop_back();
dq.push_back(n - k + 1 + 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

## # Problem C - 使数组互补的最少操作次数 (opens new window)

• $target<1+a$时，需要操作两次；
• $1+a\leq target时，需要操作一次；
• $target=a+b$时，不需要操作；
• $a+b时，需要操作一次；
• $target>b+limit$时，需要操作两次。

• $1+a$处，操作次数减少一次；
• $a+b$处，操作次数减少一次；
• $a+b+1$处，操作次数增加一次；
• $b+limit+1$处，操作次数增加一次。

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

class Solution {
public:
int minMoves(vector<int>& nums, int limit) {
int n = nums.size();
vector<int> delta(limit * 2 + 2);
for (int i = 0; i < n / 2; ++i) {
int lo = 1 + min(nums[i], nums[n - i - 1]);
int hi = limit + max(nums[i], nums[n - i - 1]);
int sum = nums[i] + nums[n - i - 1];
delta[lo]--;
delta[sum]--;
delta[sum + 1]++;
delta[hi + 1]++;
}
int now = n;
int ans = n;
for (int i = 2; i <= limit * 2; ++i) {
now += delta[i];
ans = min(ans, now);
}
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

## # Problem D - 数组的最小偏移量 (opens new window)

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

class Solution {
public:
int minimumDeviation(vector<int>& nums) {
int n = nums.size();
set<pair<int, int>> ms;
for (int i = 0; i < n; ++i) {
int num = nums[i];
while (num % 2 == 0)
num >>= 1;
ms.emplace(num, i);
}
int ans = ms.rbegin()->first - ms.begin()->first;
while (ms.begin()->first < nums[ms.begin()->second] || ms.begin()->first % 2 == 1) {
auto [num, idx] = *ms.begin();
ms.erase(ms.begin());
ms.emplace(num << 1, idx);
ans = min(ans, ms.rbegin()->first - ms.begin()->first);
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21