女装市场网站建设费用评估,网站运营工资,重庆刮刮卡制作,图片链接生成器软件打卡记录 对角线上不同值的数量差#xff08;矩阵对角线遍历 前缀和#xff09;
链接 思路#xff1a;由于任意行 i 与 列 j#xff0c;满足对角线上 i j t 的关系#xff0c;t 的范围为 [1 - n, m - 1]#xff0c;设 s t n#xff0c;可以得到 s的范围为 [1, n …打卡记录 对角线上不同值的数量差矩阵对角线遍历 前缀和
链接 思路由于任意行 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:vectorvectorint differenceOfDistinctValues(vectorvectorint grid) {int m grid.size(), n grid[0].size();vectorvectorint ans(m, vectorint(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_setint 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(vectorint 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;}
};
