打卡記錄
對(duì)角線上不同值的數(shù)量差（矩陣對(duì)角線遍歷 + 前綴和）
鏈接
思路：由于任意行 i 與 列 j，滿足對(duì)角線上 i == j + t 的關(guān)系，t 的范圍為 [1 - n, m - 1]，設(shè) s = t + n，可以得到 s的范圍為 [1, n + m - 1]，對(duì)應(yīng) m x n 矩陣上所有的 n + m - 1 條對(duì)角線，以及 i - s + n == j 的關(guān)系，根據(jù) i 的范圍 [0, m - 1] 可以推出對(duì)角線在 [1, n + m - 1] 范圍下的 j 的取值范圍，即為 [max(n - s, 0), min(n + m - s - 1, n - 1)]。
class Solution {
public:
vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> ans(m, vector<int>(n));
for (int s = 1; s <= m + n - 1; ++s) {
int min_j = max(n - s , 0), max_j = min(m + n - s - 1, n - 1);
unordered_set<int> st;
st.clear();
for (int j = min_j; j < max_j; j++) {
int i = s - n + j;
st.insert(grid[i][j]);
ans[i + 1][j + 1] = st.size();
}
st.clear();
for (int j = max_j; j > min_j; j--) {
int i = s - n + j;
st.insert(grid[i][j]);
ans[i - 1][j - 1] = abs(ans[i - 1][j - 1] - (int)st.size());
}
}
return ans;
}
};
盛最多水的容器（雙指針）
鏈接文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-722785.html
思路：若向內(nèi)移動(dòng)短板 ，水槽的短板 min(h[i],h[j]) 可能變大，因此下個(gè)水槽的面積可能增大 。若向內(nèi)移動(dòng)長(zhǎng)板 ，水槽的短板 min(h[i],h[j]) 不變或變小，因此下個(gè)水槽的面積一定變小 。因此從邊緣往內(nèi)遍歷，盡可能將短板變大，求得儲(chǔ)水最大值即為答案。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-722785.html
class Solution {
public:
int maxArea(vector<int> &height) {
int ans = 0, left = 0, right = height.size() - 1;
while (left < right) {
int area = (right - left) * min(height[left], height[right]);
ans = max(ans, area);
height[left] < height[right] ? ++left : --right;
}
return ans;
}
};
到了這里，關(guān)于Day5力扣打卡的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
