買賣股票的最佳時機II

122. 買賣股票的最佳時機 II - 力扣（LeetCode）

這里我的貪心策略是，判斷今天和前一天的股票差值，若差值大于0，則說明能獲益，即賣出，每天都比較一次，將所有差值相加即為最終能獲得的最大收益。

class Solution {
public: int maxProfit(vector<int>& prices) { int profit = 0; // 初始化利潤為0for(int i = 1; i<prices.size(); i++){ // 從數組的第二個元素開始遍歷數組if((prices[i] - prices[i-1])>0){ // 如果當前元素比前一個元素大，說明有利潤profit += prices[i] - prices[i-1]; // 累加到利潤中}}return profit; // 返回計算出的最大利潤}
};

算法的時間復雜度為O(n)，僅遍歷一次數組。

算法的空間復雜度為O(1)，只需維護常數項的空間。

跳躍游戲

55. 跳躍游戲 - 力扣（LeetCode）

定義一個變量reachmax，即能到達的最遠位置和臨時變量temp記錄在遍歷一次數組的過程中，當前能達到的最遠位置，若當前的最遠位置大于原先能到達的最遠位置，取而代之。在遍歷完后，判斷reachmax是否大于等于數組的長度，若可以，則能抵達數組的末尾，否則，返回false。

class Solution {
public:bool canJump(vector<int>& nums) {int reachmax = 1; // 初始化能夠到達的最遠位置為1，即數組的起始位置int temp = 0; // 定義一個臨時變量，用于存儲當前能夠到達的最遠位置for(int i = 0; i<nums.size();i++){ // 遍歷整個數組if(nums[i]!=0 and i < reachmax){ // 如果當前位置的值不為0，并且當前位置索引小于當前能夠到達的最遠位置temp = i + 1 + nums[i]; // 計算從當前位置能夠到達的最遠位置if(temp>reachmax){ // 如果計算出的最遠位置大于當前記錄的最遠位置reachmax = temp; // 更新能夠到達的最遠位置} }}if(reachmax>=nums.size()){ // 如果能夠到達的最遠位置大于等于數組長度，說明可以跳到終點return true;}return false; // 否則，返回false}
};

算法的時間復雜度為O(n)，遍歷一次數組。

算法的空間復雜度為O(1)，維護常數項的臨時變量和結果。

此外，可以在跳躍過程中若滿足大于等于nums.size,及時return true，能夠減少一定時間的開銷。

跳躍游戲II

45. 跳躍游戲 II - 力扣（LeetCode）

參考代碼隨想錄代碼隨想錄 (programmercarl.com)

class Solution {
public:int jump(vector<int>& nums) {if (nums.size() == 1) return 0;int curDistance = 0;    // 當前覆蓋最遠距離下標int ans = 0;            // 記錄走的最大步數int nextDistance = 0;   // 下一步覆蓋最遠距離下標for (int i = 0; i < nums.size(); i++) {nextDistance = max(nums[i] + i, nextDistance);  // 更新下一步覆蓋最遠距離下標if (i == curDistance) {                         // 遇到當前覆蓋最遠距離下標ans++;                                  // 需要走下一步curDistance = nextDistance;             // 更新當前覆蓋最遠距離下標（相當于加油了）if (nextDistance >= nums.size() - 1) break;  // 當前覆蓋最遠距到達集合終點，不用做ans++操作了，直接結束}}return ans;}
};

算法的時間復雜度O(n)

算法的空間復雜度O(1)