更新时间：2025-04-06
- 算法题解目录汇总：算法刷题记录——题解目录汇总
- 技术博客总目录：计算机技术系列博客——目录页
优先整理热门100及面试150，不定期持续更新，欢迎关注！
169. 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length1 <= n <= 5*10^4-10^9 <= nums[i] <= 10^9
进阶：
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
188. 买卖股票的最佳时机 IV
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2:
输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
方法一：动态规划（通用解法）
使用三维状态压缩的动态规划，将状态定义为 dp[j][0] 和 dp[j][1]，分别表示完成 j 次交易后不持有股票和持有股票的最大利润。通过逆序处理交易次数避免状态覆盖问题，并增加无效状态判断。
代码实现(Java)：
public class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (k == 0 || n < 2) return 0;
// 处理 k 很大的情况，退化为贪心算法
if (k >= n / 2) {
int maxProfit = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
// 动态规划初始化
int[][] prevDp = new int[k + 1][2];
for (int j = 0; j <= k; j++) {
Arrays.fill(prevDp[j], Integer.MIN_VALUE);
}
prevDp[0][0] = 0; // 0次交易，不持有股票
prevDp[0][1] = -prices[0]; // 0次交易，持有股票
for (int i = 1; i < n; i++) {
int[][] currDp = new int[k + 1][2];
for (int j = 0; j <= k; j++) {
currDp[j][0] = prevDp[j][0];
currDp[j][1] = prevDp[j][1];
}
int price = prices[i];
// 逆序处理交易次数，避免状态覆盖
for (int j = k; j >= 1; j--) {
// 不持有股票：卖出操作
if (prevDp[j][1] != Integer.MIN_VALUE) {
currDp[j][0] = Math.max(currDp[j][0], prevDp[j][1] + price);
}
// 持有股票：买入操作（需要前一次交易完成）
if (prevDp[j - 1][0] != Integer.MIN_VALUE) {
currDp[j][1] = Math.max(currDp[j][1], prevDp[j - 1][0] - price);
}
}
// 处理 j=0 的持有状态（允许第一次买入）
currDp[0][1] = Math.max(prevDp[0][1], -price);
prevDp = currDp;
}
// 寻找最大利润（所有交易次数中的最大不持有状态）
int maxProfit = 0;
for (int j = 0; j <= k; j++) {
maxProfit = Math.max(maxProfit, prevDp[j][0]);
}
return maxProfit;
}
}
复杂度分析
- 时间复杂度：
O(nk)，每个价格处理k次交易状态。 - 空间复杂度：
O(k)，使用两个数组交替保存状态。
方法二：状态压缩优化
进一步压缩动态规划空间，使用一维数组代替二维数组。通过逆序遍历交易次数减少空间使用。
代码实现(Java)：
public class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (k == 0 || n < 2) return 0;
if (k >= n / 2) {
int profit = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
int[] buy = new int[k + 1];
int[] sell = new int[k + 1];
Arrays.fill(buy, Integer.MIN_VALUE);
for (int price : prices) {
for (int j = k; j >= 1; j--) {
buy[j] = Math.max(buy[j], sell[j - 1] - price);
sell[j] = Math.max(sell[j], buy[j] + price);
}
}
return sell[k];
}
}
复杂度分析
- 时间复杂度：
O(nk)，每个价格处理k次交易。 - 空间复杂度：
O(k)，仅用两个一维数组。
声明
- 本文版权归
CSDN用户Allen Wurlitzer所有，遵循CC-BY-SA协议发布，转载请注明出处。- 本文题目来源
力扣-LeetCode，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。