力扣每日一题【2025】
记录2025年每日一题刷题过程。
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的位置，然后在前面取最大值，和后面取最大值，这样的话，算数值就是最大的。
题目一和题目二的区别就是在于测试用例的范围上。
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;
}
}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的深度达到此条件下可能的最大值。
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)
求两者是否有一个满足条件。
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
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);
}
}