文章链接
122.买卖股票的最佳时机 II
思路：
1. 核心思想：
只要明天比今天贵，就在今天买入，明天卖出，把这个差价加到总利润中。
2. 细节分析：
prices[i+1] - prices[i]表示从今天到明天能赚的利润；如果是负的（明天价格更低），
Math.Max(0, ...)会让我们不操作；如果是正的（明天价格更高），就加到利润中。
- 为什么这样能得到最大利润？
因为：
你可以进行不限次数的买卖；
那么只要有利润的地方都可以赚；
累加每一段上涨的差价，就是所有可能的收益之和；
不需要精确找波谷波峰，而是贪心抓住每一个“上涨”。
public class Solution {
public int MaxProfit(int[] prices) {
int res=0;
for(int i=0;i<prices.Length-1;i++){
res+=Math.Max(0,prices[i+1]-prices[i]);
}
return res;
}
}55. 跳跃游戏
思路：不看具体每步走了多少，要看步数的覆盖范围
维护一个变量
cover表示当前能跳到的最远位置；每次向前遍历，只要当前索引 ≤
cover，就尝试更新；时间复杂度：O(n)，空间复杂度：O(1)；
若能提前跳到终点就返回
true，否则最终返回false。
public class Solution {
public bool CanJump(int[] nums) {
int cover=0;
if(nums.Length==1) return true;
for(int i=0;i<=cover;i++){
cover=Math.Max(nums[i]+i,cover);
if(cover>=nums.Length-1) return true;
}
return false;
}
}45.跳跃游戏 II
思路：
还是和上题大致思路一致，确定覆盖范围，覆盖范围内一定可以跳到。如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。
优化：
只需要控制移动下标移动到nums.size()-2
- 如果移动下标等于当前覆盖最大距离下标， 需要再走一步（即 ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置）
- 如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。
public class Solution { public int Jump(int[] nums) { int next=0,cur=0,step=0; for(int i=0;i<nums.Length-1;i++){//优化：遍历到倒数第二位 next=Math.Max(next,nums[i]+i); if(i==cur){ cur=next; step++; } } return step; } }
1005.K次取反后最大化的数组和
思路：
第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
第二步：从前向后遍历，遇到负数将其变为正数，同时K--
第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
第四步：求和
运用到两次贪心算法：
绝对值排序后，按降序依次取反负数；
若k还有剩余且是奇数，就反转一次降序排序后的最后一个数；
public class Solution {
public int LargestSumAfterKNegations(int[] nums, int k) {
// 第一步：按绝对值从大到小排序
Array.Sort(nums,(a,b)=>Math.Abs(b).CompareTo(Math.Abs(a)));
// 第二步：从前向后把负数变成正数（k次）
for(int i=0;i<nums.Length&&k>0;i++){
if(nums[i]<0){
nums[i]*=-1;
k--;
}
}
// 第三步：如果还有剩余 k 且是奇数，翻转绝对值最小的数
if(k>0&&k%2==1){
nums[nums.Length-1]=-nums[nums.Length-1];
}
return nums.Sum();
}
}