Day5力扣打卡

打卡记录

对角线上不同值的数量差（矩阵对角线遍历 + 前缀和）

链接

思路：由于任意行 i 与 列 j，满足对角线上 i == j + t 的关系，t 的范围为 [1 - n, m - 1]，设 s = t + n，可以得到 s的范围为 [1, n + m - 1]，对应 m x n 矩阵上所有的 n + m - 1 条对角线，以及 i - s + n == j 的关系，根据 i 的范围 [0, m - 1] 可以推出对角线在 [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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

盛最多水的容器（双指针）

链接

思路：若向内移动短板 ，水槽的短板 min(h[i],h[j]) 可能变大，因此下个水槽的面积可能增大 。若向内移动长板 ，水槽的短板 min(h[i],h[j]) 不变或变小，因此下个水槽的面积一定变小 。因此从边缘往内遍历，尽可能将短板变大，求得储水最大值即为答案。

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12