记录2025年每日一题刷题过程。

2025-10

11. 盛最多水的容器（20251004）

Details

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

相向双指针。

因为老弟开始学习计算机，准备重温一下c语言的语法，顺带也贴一下c语言的代码。

Java

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int l = 0, r = n - 1;
        
        int ans = 0;
        // 判断双指针的边界
        while (l < r) {
            // 求出当前双指针所围的面积
            int s = (r - l) * Math.min(height[l], height[r]);
            // 求面积的最大值
            ans = Math.max(ans, s);
            // 那个高度矮就移动那个指针
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return ans;
    }
}

C

#define MIN(a, b) (b < a ? b : a)
#define MAX(a, b) (b > a ? b : a)

int maxArea(int* height, int heightSize) {
    int ans = 0, l = 0, r = heightSize - 1;
    while (l < r) {
        int area = (r - l) * MIN(height[l], height[r]);
        ans = MAX(ans, area);

        if (height[l] < height[r]) {
            l++;
        } else {
            r--;
        }
    }
    return ans;
}

2025-09

2221. 数组的三角和（20250930）

Details

给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是 0 到 9 之间（两者都包含）的一个数字。

nums 的 三角和 是执行以下操作以后最后剩下元素的值：

• nums 初始包含 n 个元素。如果 n == 1 ，终止 操作。否则，创建 一个新的下标从 0 开始的长度为 n - 1 的整数数组 newNums 。

• 对于满足 0 <= i < n - 1 的下标 i ，newNums[i] 赋值 为 (nums[i] + nums[i+1]) % 10 ，% 表示取余运算。

• 将 newNums 替换 数组 nums 。

• 从步骤 1 开始 重复 整个过程。

请你返回 nums 的三角和。

示例 1：

输入：nums = [1,2,3,4,5]
输出：8
解释：
上图展示了得到数组三角和的过程。

示例 2：

输入：nums = [5]
输出：5
解释：
由于 nums 中只有一个元素，数组的三角和为这个元素自己。

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 9

不用新创建newNums， 可以直接在nums上面修改。

没循环一次，把nums的长度减一

比如实例一：[1,2,3,4,5]

第一次操作： [1+2, 2+3, 3+4, 4+5] = [3, 5, 7, 9]

第二次操作：[3+5, 5+7, 7+9] = [8, 12, 16]

以此类推，知道nums只剩一个数。

Java

class Solution {
    public int triangularSum(int[] nums) {
        // 循环n-1轮
        for (int n = nums.length - 1; n > 0; n--) {
            // 为什么是i<n？因为n是下标，已经在外层循环的时候-1了
            // 这里i<n就表示 i小于数组长度-1
            for (int i = 0; i < n; i++) {
                nums[i] = (nums[i] + nums[i + 1]) % 10;
            }
        }
        return nums[0];
    }
}

1039. 多边形三角剖分的最低得分（20250929）

Details

你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。

假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。

返回 多边形进行三角剖分后可以得到的最低分 。

示例 1：

输入：values = [1,2,3]
输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。

示例 2：

输入：values = [3,7,4,5]
输出：144
解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。

示例 3：

输入：values = [1,3,1,4,1,5]
输出：13
解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。

提示：

• n == values.length
• 3 <= n <= 50
• 1 <= values[i] <= 100

简单理解题目就是，将一个多边形剖分成多个三角形，求剖分出来的三角形所有顶点乘积的和最小。

$$fn = \sum_{i=0,j=n-1}^{k} v[i] * v[j] * v[k]$$

我们以下面这个图为例来说明：

无论怎么剖分，边1-5（最下面的边）一定在一个三角形中，通过枚举这个三角形，我们可以找到这个三角形的顶点k，从而划分出来更小的子问题，就是以1-k这条边和k-5这条边在枚举其他三角形。

从而得到递推方程：

$$dfs(i, j) = \sum_{k=i+1}^{j-1} (dfs(i, k) + dfs(k, j) + v[i] * v[j] * v[k])$$

递归出口：$dfs(i, i+1) =0$，只有两个点，无法构成三角形。

函数入口：$dfs(0, n-1)$

Java

class Solution {
    int[][] memo;
    int[] v;

    public int minScoreTriangulation(int[] values) {
        v = values;
        int n = values.length;
        memo = new int[n][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(0, n - 1);
    }

    public int dfs(int i, int j) {
        if (i + 1 == j) {
            return 0;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        int res = Integer.MAX_VALUE;
        for (int k = i + 1; k < j; k++) {
            // 表示以ik为边的多边形剖分的最低分，加上以kj为边的多边形剖分的最低分，在加上当前三角形的分数
            int ans = dfs(i, k) + dfs(k, j) + v[i] * v[j] * v[k];
            res = Math.min(res, ans);
        }
        return memo[i][j] = res;
    }
}

976. 三角形的最大周长（20250928）

Details

给定由一些正数（代表长度）组成的数组 nums ，返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形，返回 0。

示例 1：

输入：nums = [2,1,2]
输出：5
解释：你可以用三个边长组成一个三角形:1 2 2。

示例 2：

输入：nums = [1,2,1,10]
输出：0
解释：
你不能用边长 1,1,2 来组成三角形。
不能用边长 1,1,10 来构成三角形。
不能用边长 1、2 和 10 来构成三角形。
因为我们不能用任何三条边长来构成一个非零面积的三角形，所以我们返回 0。

提示：

• 3 <= nums.length <= 104
• 1 <= nums[i] <= 106

枚举最长边。

我们假设三边分别是a, b, c， 并满足以下条件 1 < a < b < c

需要构成三角形，所以需要满足：

$$a + b > c \\ a + c > b \\ b + c > a$$

因为满足$1 < a < b < c$，所以$a + c > b$和$b+c>a$，都是满足的，只需要满足 $a+b > c$.

枚举c，由于a和b越大，周长越长，且$a+b>c$越能成立，所以最大周长的$a,b,c$在排序后的数组中是相邻的。

Java

class Solution {
    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        for (int i = nums.length - 1; i >= 2; i--) {
            if (nums[i - 2] + nums[i - 1] > nums[i]) {
                return nums[i - 2] + nums[i - 1] + nums[i];
            }
        }
        return 0;
    }
}

812. 最大三角形面积（20250927）

Details

给你一个由 X-Y 平面上的点组成的数组 points ，其中 points[i] = [xi, yi] 。从其中取任意三个不同的点组成三角形，返回能组成的最大三角形的面积。与真实值误差在 10-5 内的答案将会视为正确答案**。**

示例 1：

输入：points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
输出：2.00000
解释：输入中的 5 个点如上图所示，红色的三角形面积最大。

示例 2：

输入：points = [[1,0],[0,0],[0,1]]
输出：0.50000

提示：

• 3 <= points.length <= 50
• -50 <= xi, yi <= 50
• 给出的所有点 互不相同

对于平面上的3各点 p1, p2, p3， 定义两个向量 $a = \vec{p_1p_2}$ , $b=\vec{p_1p_3}$

• 向量1：从p1指向p2 → (x1, y1) = (p2_x - p1_x, p2_y - p1_y)
• 向量2：从p1指向p3 → (x2, y2) = (p3_x - p1_x, p3_y - p1_y)

根据向量叉积定义，三角形面积：

$$S = \frac{1}{2}|x_1y_2 - x_2y_1|$$

Java

class Solution {
    public double largestTriangleArea(int[][] points) {
        int n = points.length;
        int ans = 0;

        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    int[] p1 = points[i], p2 = points[j], p3 = points[k];
                    int x1 = p2[0] - p1[0], y1 = p2[1] - p1[1];
                    int x2 = p3[0] - p1[0], y2 = p3[1] - p1[1];
                    ans = Math.max(ans, Math.abs(x1 * y2 - x2 * y1));
                }
            }
        }
        return ans / 2.0;
    }
}

120. 三角形最小路径和（20250926）

Details

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

提示：

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -104 <= triangle[i][j] <= 104

题目要求从第一排到最后一排最小的路径之和。

2
3 4
6 5 7
4 1 8 3

通过示例，就很容易看出来了。我们要解决的问题就是：从最上面（0, 0）出发，移动到triangle的最后一排，路径上面元素和最小。

考虑下一步往那里走：

• 走到(1,0)， 那么需要解决的问题为：从(1,0)出发，移动到triangle最后一排，路径最小和
• 走到(1,1)，那么需要解决的问题为：从(1,1)出发，移动到triangle最后一排，路径最小和。

这些问题都是和原问题相似、规模更小的问题，可以用递归解决。

递推函数：

$$dfs(i, j) = min(dfs(i+1, j), dfs(i+1, j+1)) + triangle[i][j]$$

Java

class Solution {
    int[][] memo;

    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        memo = new int[n][n];
        for (int[] row : memo) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }
        return dfs(triangle, 0, 0);
    }

    public int dfs(List<List<Integer>> triangle, int i, int j) {
        // 当达到最后一行的时候，递归出口
        if (i == triangle.size() - 1) {
            return triangle.get(i).get(j);
        }
        if (memo[i][j] != Integer.MIN_VALUE) {
            return memo[i][j];
        }
        return memo[i][j] = Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);
    }
}

2025-08

3195. 包含所有 1 的最小矩形面积 I（20250822）

Details

给你一个二维 二进制 数组 grid。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。

返回这个矩形可能的 最小 面积。

示例 1：

输入： grid = [[0,1,0],[1,0,1]]

输出： 6

解释：

这个最小矩形的高度为 2，宽度为 3，因此面积为 2 * 3 = 6。

示例 2：

输入： grid = [[0,0],[1,0]]

输出： 1

解释：

这个最小矩形的高度和宽度都是 1，因此面积为 1 * 1 = 1。

提示：

• 1 <= grid.length, grid[i].length <= 1000
• grid[i][j] 是 0 或 1。
• 输入保证 grid 中至少有一个 1 。

遍历grid：

• 找到最左边最右边的1的列号，分别记作left， right， 则举行底边长至少为right-left+1
• 找到最上边最下边的1的行号，分别记作top，bottom，则矩形的高至少为bottom-top+1

矩形的面积至少为：

$$S = (right - left + 1) * (bottom - top + 1)$$

Java

class Solution {
    public int minimumArea(int[][] grid) {
        // 为什么left和top默认要取最大值
        // 因为这样方便取最小值
        int left = Integer.MAX_VALUE;
        int right = 0;
        int top = Integer.MAX_VALUE;
        int bottom = 0;

        int n = grid.length, m = grid[0].length;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    left = Math.min(left, j);
                    right = Math.max(right, j);
                    top = Math.min(top, i);
                    bottom = Math.max(bottom, i);
                }
            }
        }
        return (right - left + 1) * (bottom - top + 1);

    }
}

342. 4的幂（20250815）

Details

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x

示例 1：

输入：n = 16
输出：true

示例 2：

输入：n = 5
输出：false

示例 3：

输入：n = 1
输出：true

提示：

• -231 <= n <= 231 - 1

**进阶：**你能不使用循环或者递归来完成本题吗？

原本以为使用之前3的幂就能解，确实能解，但是耗时比较长，就来学习学习其他题解的解题方式。

是4的次幂，那么一定是2的次幂，就需要用到2的次幂的知识点来判断，就是2的次幂的二进制表示中，只有一个1 ， 使用 n & (n-1)一定等于0，然后才是判断是否是4的次幂

1 = 1

4 = 100

16 = 10000

参考灵神的题解；两种方法：位运算 / 数学（Python/Java/C++/C/Go/JS/Rust）

1780. 判断一个数字是否可以表示成三的幂的和（20250814）

Details

给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true ，否则请返回 false 。

对于一个整数 y ，如果存在整数 x 满足 y == 3x ，我们称这个整数 y 是三的幂。

示例 1：

输入：n = 12
输出：true
解释：12 = 31 + 32

示例 2：

输入：n = 91
输出：true
解释：91 = 30 + 32 + 34

示例 3：

输入：n = 21
输出：false

提示：

• 1 <= n <= 107

看到这个问题，最开始想到的是使用动态规划来处理，但是没写出来，可以后面尝试一下。

还是需要参考灵神的题解：三进制分解

大概的意思就是，将n用3进制形式表示，比如12 = 110, 21=210，然后对三进制判断，如果3进制中有数字2, 那么就没办法满足条件情况，返回false，否则返回true。

想想我们在取10进制数的每一位的时候，是怎么处理的，首先是取余数， n % 10， 然后在将 n /= 10，进入到下一位的运算，我们也可以这样弄。

遍历3进制的每一位，先对3取余数，n % 3， 然后在 n /= 3。

因为对3取余数的话，结果只可能是0, 1, 2 ，不会有在大的结果了。

Java

class Solution {
    public boolean checkPowersOfThree(int n) {
        while (n > 0) {
            if (n % 3 == 2) {
                return false;
            }
            n /= 3;
        }
        return true;
    }
}

326. 3 的幂（20250813）

Details

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

示例 1：

输入：n = 27
输出：true

示例 2：

输入：n = 0
输出：false

示例 3：

输入：n = 9
输出：true

示例 4：

输入：n = 45
输出：false

提示：

• -231 <= n <= 231 - 1

题目给出一个n，判断n是否是3的幂次方。

第一种解题方式就是使用试除法，因为是3的幂次方，每次除以，相当于幂次方-1.

第二种方式是通过条件边界来处理，因为n是2³¹-1， 最大的n就是3⁹，所以如果是3的幂次方的话， n一定是3⁹的因子。

试除法

class Solution {
    public boolean isPowerOfThree(int n) {
        while (n != 0 && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
}

最大幂的约数

class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && Math.pow(3, 9) % n == 0;
    }
}

相似的题目还有：

• 231. 2 的幂
• 342. 4的幂

2787. 将一个数字表示成幂的和的方案数（20250812）

Details

请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1x + n2x + ... + nkx 。

由于答案可能非常大，请你将它对 109 + 7 取余后返回。

比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 23 + 33 + 53 。

示例 1：

输入：n = 10, x = 2
输出：1
解释：我们可以将 n 表示为：n = 32 + 12 = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。

示例 2：

输入：n = 4, x = 1
输出：2
解释：我们可以将 n 按以下方案表示：
- n = 41 = 4 。
- n = 31 + 11 = 4 。

提示：

• 1 <= n <= 300
• 1 <= x <= 5

终于是把这道题磨出来了，还是在看了题解的情况下，才把记忆化搜索的代码写出来了。

题目要求求出互不相同的正整数的x次幂的和等于n的方案数，所以可以把n看作是背包的总量，每个正整数的x次幂看作是物品，这样的话，我们就可以使用01背包的思路来解了。

这里的x大于等于1, 小于等于5, 所以最大的正整数就是当x等于1时，正整数等于n。

Java

class Solution {
    int[][] memo;
    int x;

    public int numberOfWays(int n, int x) {
        memo = new int[n + 1][n + 1];
        for (int[] m : memo) {
            Arrays.fill(m, -1);
        }
        this.x = x;
        return dp(n, n);
    }

    private int dp(int i, int n) {
        if (i == 0) {
            return n == 0 ? 1 : 0;
        }
        if (memo[i][n] != -1) {
            return memo[i][n];
        }
        int t = (int) Math.pow(i, x);

        // not choice
        int res = dp(i - 1, n);
        if (n >= t) {
            // choice
            res += dp(i - 1, n - t);
        }
        // 因为结果比较大，需要对结果取余
        return memo[i][n] = res % 1_000_000_007;
    }
}

118. 杨辉三角（20250801）

Details

给定一个非负整数 *numRows，*生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

• 1 <= numRows <= 30

题目就是要求我们输出高度为numRows的杨辉三角的所有值。

把杨辉三角的每一排对齐：

[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]

设要计算的二维数组是c，计算方法如下：

• 每一排的第一个数和最后一个数都是1，即$c[i][0]=c[i][i] =1$
• 其余数字，等于左上方的数，加上正上方的数，即$c[i][j]=c[i-1][j-1] + c[i-1][j]$

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> c = new ArrayList<>();
        c.add(List.of(1));
        for (int i = 1; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            row.add(1);
            // i 就是每一行的个数
            for (int j = 1; j < i; j++) {
                int t = c.get(i - 1).get(j - 1) + c.get(i - 1).get(j);
                row.add(t);
            }
            row.add(1);
            c.add(row);
        }
        return c;
    }
}

还有一种方法就是使用动态规划来求解，就是使用动态规划来做，现在还不会，带我学习一下。

2025-07

2683. 相邻值的按位异或（20250731）

Details

下标从 0 开始、长度为 n 的数组 derived 是由同样长度为 n 的原始 二进制数组 original 通过计算相邻值的 **按位异或（⊕）**派生而来。

特别地，对于范围 [0, n - 1] 内的每个下标 i ：

• 如果 i = n - 1 ，那么 derived[i] = original[i] ⊕ original[0]
• 否则 derived[i] = original[i] ⊕ original[i + 1]

给你一个数组 derived ，请判断是否存在一个能够派生得到 derived 的 有效原始二进制数组 original 。

如果存在满足要求的原始二进制数组，返回 true ；否则，返回 false 。

• 二进制数组是仅由 0 和 1 组成的数组。

示例 1：

输入：derived = [1,1,0]
输出：true
解释：能够派生得到 [1,1,0] 的有效原始二进制数组是 [0,1,0] ：
derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1 
derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0

示例 2：

输入：derived = [1,1]
输出：true
解释：能够派生得到 [1,1] 的有效原始二进制数组是 [0,1] ：
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1

示例 3：

输入：derived = [1,0]
输出：false
解释：不存在能够派生得到 [1,0] 的有效原始二进制数组。

提示：

• n == derived.length
• 1 <= n <= 105
• derived 中的值不是 0 就是 1 。

没想到今天就是7月的最后一天了，也是真的过的快，已经快3个月没有做算法题了。

今天这道题，就是通过递推出来公式，然后求解。

我们就用实例1，给出来的解释来做：

$derived[0] = original[0] ⊕ original[1]$

$derived[1] = original[1] ⊕ original[2]$

$derived[2] = original[2] ⊕ original[0]$

然后我们把两边同时都异或上，就会得到下面的公式：

$derived[0] ⊕ derived[1] ⊕ derived[2]= original[0] ⊕ original[1] ⊕ original[1] ⊕ original[2] ⊕ original[2] ⊕ original[0]$

然后就有，判断$derived[0] ⊕ derived[1] ⊕ derived[2] $是否等于0，来判断是否有这样一个数组，通过题目给出的算法，计算出来derived。

class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        int xor  =0;
        for(int x: derived){
            xor ^= x;
        }
        return xor == 0;
    }
}

我们还需要知道一些疑惑的小技巧：

• 两个相同的数xor结果为0

2025-04

2874. 有序三元组中的最大值 II（20250402更新）

这里还有一道相同题目的简单题：2873. 有序三元组中的最大值 I

这两道题是第 365 场周赛题目，感兴趣的可以看下。

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

开始想到的就是确定j的位置，然后在前面取最大值，和后面取最大值，这样的话，算数值就是最大的。

题目一和题目二的区别就是在于测试用例的范围上。

枚举 J

class Solution {
    public long maximumTripletValue(int[] nums) {
        // 计算前缀最大值和后缀最大值
        int n = nums.length;
      
      	// 计算后缀最大值，需要从右往左遍历，因为是求的[j+1, n-1]的最大值
        int[] sufMax = new int[n];
        sufMax[n - 1] = nums[n - 1];
        for (int j = n - 2; j >= 0; j--) {
            sufMax[j] = Math.max(sufMax[j + 1], nums[j]);
        }
      
      	// 计算前缀还好，就是从前往后遍历，通过preMax[i] = max(preMax[i-1], nums[i])
        int[] preMax = new int[n];
        preMax[0] = nums[0];
        for (int j = 1; j < n; j++) {
            preMax[j] = Math.max(preMax[j - 1], nums[j]);
        }
      	// 根据题目意思计算方程式的值
        long mx = 0;
        for (int j = 1; j < n - 1; j++) {
            long sum = (long) (preMax[j - 1] - nums[j]) * sufMax[j + 1];
            mx = Math.max(mx, sum);
        }
        return mx;
    }
}

枚举 K

class Solution {
    public long maximumTripletValue(int[] nums) {
        long ans = 0;
        long maxDiff = 0;
        long preMax = 0;

        for (int x : nums) {
            // 先把x当作nums[k]
            ans = Math.max(ans, maxDiff * x);
            // 在把x当作nums[j]
            maxDiff = Math.max(maxDiff, preMax - x);
            // 在把x当作nums[i]
            preMax = Math.max(preMax, x);
        }
        return ans;
    }
}

121. 买卖股票的最佳时机（20250403更新）

今天的每日一题是有序三元组II，昨天已经做过了，今天把买卖股票作为每日一题题目。

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

根据题意我们知道，想要获取的利润最大的话，我们就需要买的时候尽可能的小， 买的时候尽可能的大，所以就可以通过维护前缀最小值，或者维护后缀最大值的方式来求解。

维护前缀最小值

class Solution {
  	// 维护前缀最小值 方法一
  	// 通过使用数组，将每一个prices[i]的前缀最小值都维护起来, 空间复杂度O(n)
  	public int maxProfit(int[] prices) {
        // 对每一个prices[i]维护最小前缀值
        int n = prices.length;
        int[] preMin = new int[n];

        preMin[0] = prices[0];
        for (int i = 1; i < n; i++) {
            preMin[i] = Math.min(preMin[i - 1], prices[i]);
        }
        // 枚举卖出价格，计算最终结果
        int ans = 0;
        for (int i = 1; i < n; i++) {
            ans = Math.max(ans, prices[i] - preMin[i - 1]);
        }
        return ans;
    }
  	// 维护前缀最小值 方法二
  	// 通过变量，值维护当前prices[i]的前缀最小值，优化空间复杂度为O(1)
    public int maxProfit(int[] prices) {
        // 从左到右遍历的时候，同时维护前缀最小值minPrice
        int ans = 0, minPrice = prices[0];
        for (int p : prices) {
            ans = Math.max(ans, p - minPrice);
            minPrice = Math.min(minPrice, p);
        }
        return ans;
    }
}

维护后缀最大值

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] sufMax = new int[n];
        sufMax[n - 1] = prices[n - 1];
      	// 计算最大后缀数组
        for (int i = n - 2; i >= 0; i--) {
            sufMax[i] = Math.max(sufMax[i + 1], prices[i]);
        }
      	// 计算最终结果
        int ans = 0;
        for (int i = 0; i < n - 1; i++) {
            ans = Math.max(ans, sufMax[i + 1] - prices[i]);
        }
        return ans;
    }
}

1123. 最深叶节点的最近公共祖先（20250404更新）

给你一个有根节点 root 的二叉树，返回它 最深的叶节点的最近公共祖先 。

回想一下：

• 叶节点 是二叉树中没有子节点的节点
• 树的根节点的 深度 为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1
• 如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。

Java

class Solution {
    private TreeNode ans;
    private int maxDepth = -1;

    public TreeNode lcaDeepestLeaves(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    int dfs(TreeNode node, int depth) {
        if (node == null) {
            maxDepth = Math.max(maxDepth, depth);
            return depth;
        }
        int leftMaxDepth = dfs(node.left, depth + 1);
        int rightMaxDepth = dfs(node.right, depth + 1);

        if (leftMaxDepth == rightMaxDepth && leftMaxDepth == maxDepth) {
            ans = node;
        }
        return Math.max(leftMaxDepth, rightMaxDepth);
    }
}

416. 分割等和子集（20250407更新）

标签：数组、动态规划

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

统计数组总和；如果和为奇数，直接返回false；加入记忆化搜索数组。

设数组总和为s，求能否从nums中选出一个子序列，其元素的和恰好等于s/2。

开始定义dfs(target)，表示求和为target的答案，但是和nums的元素关联不上，后面看了题解，将dfs修改成dfs(i, j)，表示从nums[0]到nums[i]中，是否存在和为j的子序列。

考虑选或者不选nums[i]的情况，就得到递推公式：

• 选： dfs(i-1, j-nums[i])
• 不选：dfs(i-1, j)

求两者是否有一个满足条件。

Java

class Solution {
    public boolean canPartition(int[] nums) {
        // 计算数组和
        int s = 0;
        for (int x : nums) {
            s += x;
        }
        // 如果和为奇数直接返回false
        if (s % 2 != 0) {
            return false;
        }
        // 初始化记忆化搜索数组
        int n = nums.length;
        int[][] memo = new int[n][s / 2 + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        // 
        return dfs(n - 1, s / 2, nums, memo);
    }

    boolean dfs(int i, int j, int[] nums, int[][] memo) {
        if (i < 0) {
            return j == 0;
        }
        if (memo[i][j] != -1) {
            return memo[i][j] == 1;
        }
        // 选或者不选
        boolean res = j >= nums[i] && dfs(i - 1, j - nums[i], nums, memo) || dfs(i - 1, j, nums, memo);
        memo[i][j] = res ? 1 : 0;
        return res;

    }
}

编码过程中的困难点：

• 1、记忆化搜索数组memo是定义成int还是boolean类型？如何初始化？
  • 定义成int，初始化的时候默认-1， 这样在时候是就可以判断memo[i][j]是否等于-1；boolean不好判断。
  • 初始化只能每一层Arrays.fill(row, -1)来初始化。

3396. 使数组元素互不相同所需的最少操作次数（20250408更新）

标签：数组、哈希表

给你一个整数数组 nums，你需要确保数组中的元素 互不相同 。为此，你可以执行以下操作任意次：

• 从数组的开头移除 3 个元素。如果数组中元素少于 3 个，则移除所有剩余元素。

**注意：**空数组也视作为数组元素互不相同。返回使数组元素互不相同所需的 最少操作次数 。

如果存在重复的值，每次移除前面三个元素，也就是移除数组的前缀，那么剩下的一定是nums的后缀，那么问题就变成了，求最长不重复的nums的后缀元素。

当第i个元素重复，那么前面下标从0到i的话就有i+1个元素，除以3上取整的话，通过转化就得到了结果：i/3 + 1

上取整下取整转换公式的证明

Java

class Solution {
    public int minimumOperations(int[] nums) {
        // 求nums的最长无重复元素后缀
        Set<Integer> seen = new HashSet<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            // set.add 添加成功之后返回true， 添加失败返回false
            if (!seen.add(nums[i])) {
                // (i+1)/3上取整 = i/3下去整+1
                return i / 3 + 1;
            }
        }
        return 0;
    }
}

3375. 使数组的值全部为 K 的最少操作次数（20250409更新）

标签：数组、哈希表

给你一个整数数组 nums 和一个整数 k 。

如果一个数组中所有 严格大于 h 的整数值都 相等 ，那么我们称整数 h 是 合法的 。

比方说，如果 nums = [10, 8, 10, 8] ，那么 h = 9 是一个 合法 整数，因为所有满足 nums[i] > 9 的数都等于 10 ，但是 5 不是 合法 整数。

你可以对 nums 执行以下操作：

• 选择一个整数 h ，它对于 当前 nums 中的值是合法的。
• 对于每个下标 i ，如果它满足 nums[i] > h ，那么将 nums[i] 变为 h 。

你的目标是将 nums 中的所有元素都变为 k ，请你返回 最少 操作次数。如果无法将所有元素都变 k ，那么返回 -1 。

真心觉得自己做题看到的就是题，灵神做题真的是连题目的裤衩都看透了😂。

题目的本质就是统计次大值的个数min(nums)和k的之间的关系， distinctCount表示数组中不同的元素个数

• k > min(nums)，无法满足直接返回-1
• k == min(nums) ，返回dictinctCount - 1
• k < min(nums), 返回distinctCount

自己写的代码

class Solution {
    public int minOperations(int[] nums, int k) {
        // 如果数组中有小于k的值，就没办法
        Arrays.sort(nums);

        for (int x : nums) {
            if (x < k) {
                return -1;
            }
        }
        // 每次取次大值，然后把最大值修改成次大值
        int n = nums.length;
        int cnt = 0;
        int mx = nums[n - 1];

        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] < mx) {
                mx = nums[i];
                cnt++;
            }
            // 最后判断当i=0时，nums[i]是否大于k，大于k时还需要增加一次操作。
            if (i == 0 && nums[i] > k) {
                cnt++;
            }
        }
        return cnt;

    }
}

灵神写的代码

class Solution {
    public int minOperations(int[] nums, int k) {
        // 如果 k>min(nums)，无法满足要求，返回 −1。
        int min = Arrays.stream(nums).min().getAsInt();
        if (min < k) {
            return -1;
        }
        // 如果 k=min(nums)，操作次数为 nums 中的不同元素个数减一。比如 [5,2,5,4,5]→[4,2,4,4,4]→[2,2,2,2,2]，最大值 5→4→2，用了 2 次操作。
        // 如果 k<min(nums)，操作次数为 nums 中的不同元素个数。因为都变成 min(nums) 后，还需要再操作一次，才能都变成 k。
        int distinceCount = (int) Arrays.stream(nums).distinct().count();
        // return k == min? distinceCount - 1: distinceCount;
        return distinceCount - (k == min ? 1 : 0);
    }
}

Changelog

10/10/25, 3:04 PM

View All Changelog

• 1ee1e-feat(wiki): algo -on 10/10/25