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;}
};

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

链接

思路：若向内移动短板，水槽的短板 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;}
};