# # Leetcode 第28场双周赛题解

## # Problem A - 商品折扣后的最终价格 (opens new window)

### # 方法一：暴力

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

class Solution {
public:
vector<int> finalPrices(vector<int>& prices) {
int n = prices.size();
vector<int> ans(prices);
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (prices[j] <= prices[i]) {
ans[i] -= prices[j];
break;
}
return ans;
}
};

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

### # 方法二：单调栈

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

class Solution {
public:
vector<int> finalPrices(vector<int>& prices) {
int n = prices.size();

stack<int> st;
vector<int> next_smaller(n, -1);

for (int i = 0; i < n; ++i) {
while (!st.empty() && prices[st.top()] >= prices[i]) {
next_smaller[st.top()] = i;
st.pop();
}
st.push(i);
}

vector<int> ans(prices);
for (int i = 0; i < n; ++i)
if (next_smaller[i] != -1)
ans[i] -= prices[next_smaller[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

## # Problem B - 子矩形查询 (opens new window)

### # 方法一：模拟

• 时间复杂度：update为$\mathcal{O}(RC)$，get为$\mathcal{O}(1)$
• 空间复杂度$\mathcal{O}(RC)$

class SubrectangleQueries {
vector<vector<int>> rectangle;
public:
SubrectangleQueries(vector<vector<int>>& rectangle): rectangle(rectangle) {}

void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
for (int i = row1; i <= row2; ++i)
for (int j = col1; j <= col2; ++j)
rectangle[i][j] = newValue;
}

int getValue(int row, int col) {
return rectangle[row][col];
}
};

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

### # 方法二：记录操作历史而非改变数组的值

• 时间复杂度：update为$\mathcal{O}(1)$，get为$\mathcal{O}(Q)$
• 空间复杂度$\mathcal{O}(RC+Q)$

class SubrectangleQueries {
vector<vector<int>> rectangle;
vector<tuple<int, int, int, int, int>> history;
public:
SubrectangleQueries(vector<vector<int>>& rectangle): rectangle(rectangle) {}

void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
history.emplace_back(row1, col1, row2, col2, newValue);
}

int getValue(int row, int col) {
int n = history.size();
for (int i = n - 1; i >= 0; --i) {
auto [row1, col1, row2, col2, newValue] = history[i];
if (row1 <= row && row <= row2 && col1 <= col && col <= col2)
return newValue;
}
return rectangle[row][col];
}
};

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

## # Problem C - 找两个和为目标值且不重叠的子数组 (opens new window)

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

def solve(arr: List[int], target: int):
n = len(arr)

d = {0: 0}
s = 0

ans = [n + 1] * n

for i in range(n):
s += arr[i]
if (s - target) in d:
ans[i] = i + 1 - d[s - target]
d[s] = i + 1

for i in range(1, n):
ans[i] = min(ans[i], ans[i - 1])

return ans

class Solution:
def minSumOfLengths(self, arr: List[int], target: int) -> int:
n = len(arr)
l = solve(arr, target)
r = solve(arr[::-1], target)[::-1]
ans = n + 1
for i in range(n - 1):
if l[i] < n and r[i + 1] < n:
ans = min(ans, l[i] + r[i + 1])
return -1 if ans == n + 1 else 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

## # Problem D - 安排邮筒 (opens new window)

1. 邮筒应该放在某个房屋处，因为这样的总成本不会高于放在路中间的成本。
2. 任意两个邮筒的服务范围是不重叠的。

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

const int INF = 0x3f3f3f3f;

class Solution {
int dp[105][105];
public:
int minDistance(vector<int>& houses, int k) {
int n = houses.size();
sort(houses.begin(), houses.end());
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
vector<vector<int>> dist(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j)
for (int l = i, r = j; l < r; l++, r--)
dist[i][j] += houses[r - 1] - houses[l - 1];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= min(i, k); ++j) {
for (int p = 0; p <= i - 1; ++p)
dp[i][j] = min(dp[i][j], dp[p][j - 1] + dist[p + 1][i]);
}
return dp[n][k];
}
};

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