目录
LeetCode.122 买卖股票的最佳时机 II
题目链接 买卖股票的最佳时机 II
题解
class Solution {
public int maxProfit(int[] prices) {
int res = 0;
for(int i = 0;i<prices.length-1;i++){
int tmp = prices[i+1] - prices[i];
if(tmp > 0) res += tmp;
}
return res;
}
}解题思路
这段代码实现了一个计算股票最大利润的算法。它采用了一种 "贪心" 策略，通过捕捉每一个上涨的机会来实现最大利润。
算法的核心思想是：只要第二天的股价高于当天股价，就进行一次交易（当天买入，第二天卖出），将所有这些正的差价累加起来，就得到了最大利润。
这种方法的时间复杂度是 O (n)，其中 n 是股票价格数组的长度，因为只需要遍历一次数组。空间复杂度是 O (1)，只使用了常数个额外变量。
这个解法适用于 "可以进行多次交易，但不能同时参与多笔交易" 的场景，也就是必须在卖出股票后才能再次买入。
LeetCode.55 跳跃游戏
题目链接 跳跃游戏
题解
class Solution {
public boolean canJump(int[] nums) {
int range = 0;
for(int i = 0;i<=range;i++){
range = Math.max(range,i + nums[i]);
if(range >= nums.length-1) return true;
}
return false;
}
}解题思路
这段代码实现了判断能否到达数组最后一个位置的功能，采用了贪心算法的思想，效率较高。
算法的核心思路是：
- 维护一个变量
range，表示当前能够到达的最远索引位置 - 遍历数组，对于每个索引
i，如果i在当前可到达范围内，就更新range为i + nums[i]（从当前位置能到达的最远位置）和原range中的较大值 - 如果在遍历过程中，
range已经大于等于数组最后一个索引，说明能到达终点，直接返回true - 如果循环结束后仍未到达终点，则返回
false
这种解法的时间复杂度是 O (n)，只需要遍历一次数组；空间复杂度是 O (1)，只使用了常数个额外变量。
LeetCode.45 跳跃游戏 II
题目链接 跳跃游戏 II
题解
class Solution {
public int jump(int[] nums) {
if(nums.length == 1) return 0;
int curRange = 0;
int maxRange = 0;
int count = 0;
for(int i = 0;i<=curRange;i++){
maxRange = Math.max(maxRange,nums[i] + i);
if(maxRange >= nums.length - 1){
count ++;
break;
}
if(i == curRange){
curRange = maxRange;
count ++;
}
}
return count;
}
}解题思路
这段代码实现了求解 "跳跃游戏 II" 的功能，即计算从数组第一个位置跳到最后一个位置所需的最少跳跃次数。这是一道经典的贪心算法应用题目。
算法的核心思路是：
- 维护两个变量：
curRange表示当前跳跃所能到达的最远位置，maxRange表示在当前可到达范围内，下一步能跳的最远位置 - 遍历数组，不断更新
maxRange为当前能到达的最远位置 - 当遍历到
curRange的边界时，说明需要进行一次跳跃，将curRange更新为maxRange，并增加跳跃次数 - 如果在任何时候
maxRange已经覆盖了数组最后一个位置，再跳一次即可到达终点
具体步骤解析：
- 特殊情况处理：如果数组长度为 1，无需跳跃，直接返回 0
- 遍历数组中当前可到达的范围（
i <= curRange） - 每次更新
maxRange为当前位置能到达的最远点 - 当
maxRange覆盖终点时，增加一次跳跃次数并结束循环 - 当到达当前跳跃范围的边界时，进行一次跳跃（更新
curRange和count）
该算法的时间复杂度是 O (n)，只需要遍历一次数组；空间复杂度是 O (1)，仅使用了常数个额外变量。
LeetCode.1005 K次取反后最大化的数组和
题目链接 K次取反后最大化的数组和
题解
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(
Arrays.stream(nums).boxed().collect(Collectors.toList())
);
for(int i = 0;i<k;i++){
int tmp = - minHeap.poll();
minHeap.offer(tmp);
}
int res = 0;
while (!minHeap.isEmpty()) {
res += minHeap.poll();
}
return res;
}
}解题思路
这段代码实现了 "K 次取反后最大化的数组和" 的解决方案，采用了优先队列（最小堆）来高效处理。
算法的核心思路是：
- 将数组元素放入最小堆，这样可以每次快速获取当前最小的元素
- 进行 K 次取反操作：每次取出最小的元素，取反后再放回堆中
- K 次操作完成后，将堆中所有元素求和，即为最大化的数组和
这种方法的原理是：要最大化数组和，应该优先对最小的元素进行取反（尤其是负数），因为这会带来最大的增益。即使所有元素都是正数，也应该对最小的正数进行反复取反（如果 K 是奇数）。
时间复杂度分析：
- 构建最小堆的时间复杂度是 O (n)
- 每次堆操作（取出和放入）的时间复杂度是 O (log n)
- 总时间复杂度是 O (n + K log n)
空间复杂度是 O (n)，用于存储堆中的元素。