LeetCode刷题记录（贪心算法篇）

LeetCode刷题记录（贪心算法篇），个人向。

[121] Best Time to Buy and Sell Stock

难度：Easy
语言：C++

题目描述。
遍历一遍数组即可。其中记录一下历史价格最低值，然后查看当前价格减去历史最低值（即当前利润）是否大于最大利润即可，最后返回最大利润。

class Solution {
  public:
    int maxProfit(vector<int> &prices) {
        int max_profit = 0;
        int buy = prices[0];

        for (int p : prices) {
            if (p <= buy) {
                buy = p;
            } else if (p - buy > max_profit) {
                max_profit = p - buy;
            }
        }

        return max_profit;
    }
};

[55] Jump Game

难度：Medium
语言：C++

题目描述。
这道题只要想清楚，我们不需要关心怎么从起点跳到终点，只需要知道能不能跳到终点，这道题就变得很简单。
我们可以在遍历数组的同时更新能跳到的位置的覆盖范围（覆盖到了，就说明能跳到这里，怎么跳的不关心），最后看覆盖的范围有没有到最后一个位置即可。

class Solution {
  public:
    bool canJump(vector<int> &nums) {
        int curPos = 0;
        int maxJump = 0;
        int dest = nums.size() - 1;
        while (maxJump < dest && curPos <= maxJump) {
            maxJump = max(maxJump, curPos + nums[curPos]);
            curPos += 1;
        }
        return maxJump >= dest;
    }
};

[45] Jump Game II

难度：Medium
语言：C++

题目描述。
相比上一题，这题需要记录步数。
我们依然不用关注是如何跳到终点的，即不需要关注具体路径。
相比上一题，我们需要分别记录一下当前step能到达的最远距离curMaxPos和下一step能到达的最远距离nextMaxPos，然后在curPos到达curMaxPos时说明当前step已经走完，nextMaxPos已经更新完毕，此时更新一下step和curMaxPos，开始下一轮迭代。
注意for循环判断条件为curMaxPos < dest而不是nextMaxPos < dest，否则最终step可能会少一。

class Solution {
  public:
    int jump(vector<int> &nums) {
        int step = 0;
        int curMaxPos = 0;
        int nextMaxPos = 0;
        int dest = nums.size() - 1;

        for (int curPos = 0; curMaxPos < dest; ++curPos) {
            nextMaxPos = max(nextMaxPos, curPos + nums[curPos]);
            if (curPos == curMaxPos) {
                step += 1;
                curMaxPos = nextMaxPos;
            }
        }

        return step;
    }
};

[763] Partition Labels

难度：Medium
语言：C++

题目描述。
和贪心好像没多大关系。
先遍历一遍字符串，统计各个字符的最远出现位置。
然后，第二次遍历字符串，遍历同时记录一下遍历到的字符的最远出现下标（end = max(end, map[s[i] - 'a']);）。当遍历到达记录的遍历过字符的最远出现下标了，就说明当前片段遍历结束，记录一下结果（end - start + 1），然后开始下一片段（start = end + 1;）。

class Solution {
  public:
    vector<int> partitionLabels(string s) {
        int length = s.size();
        int map[26] = {0};
        int start = 0, end = 0;
        vector<int> result;
        for (int i = 0; i < length; ++i) {
            map[s[i] - 'a'] = i;
        }

        for (int i = 0; i < length; ++i) {
            end = max(end, map[s[i] - 'a']);
            if (i == end) {
                result.push_back(end - start + 1);
                start = end + 1;
            }
        }

        return result;
    }
};

总结

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

对于121来说，我们计算当前的最大利润，最后得到整体的最大利润。
对于55来说，我们计算当前能够跳到的最大范围，最后得到整体能跳到的最大范围，再看是否覆盖了终点位置。
对于45来说，我们根据上一step能跳到的最大距离来计算当前step能跳到的最大距离，最后返回跳到终点时（即整体）的step数。
763和贪心关系不大。硬要说的话，我们通过统计当前遍历过字符的最远出现位置，最后得到当前片段整体的终止位置。

补充

[53] Maximum Subarray

难度：Medium
语言：C++

题目描述。
当当前子数组和为负值，则立即抛弃当前累加过的值，直接以下一个数字为新的起点。过程中记录最大子数组和即可。
这道题也可用动态规划的思想，参考maxSubArrayDP。但动态规划需要 $O(n)$ 的空间复杂度，所以还不如贪心了。这里动态规划中dp[i]也只与dp[i-1]相关，所以我们也可以把贪心的方式理解成是给动态规划的方法做了空间上的优化得到。

class Solution {
  public:
    int maxSubArray(vector<int> &nums) {
        int result = nums[0];
        int count = 0;

        for (const int &num : nums) {
            count += num;
            result = max(result, count);
            count = max(count, 0);
        }

        return result;
    }

    int maxSubArrayDP(vector<int> &nums) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        int result = nums[0];
        for (int i = 1; i < n; ++i) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            result = max(result, dp[i]);
        }
        return result;
    }
};

[56] Merge Intervals

难度：Medium
语言：C++

题目描述。
先按照起点排序，然后看当前终点是否超过intervals[i+1]的起点。若不超过，说明两个区间没有重叠，压一下结果并更新一下起点。过程中不断更新终点。

class Solution {
  public:
    vector<vector<int>> merge(vector<vector<int>> &intervals) {
        int n = intervals.size();
        vector<vector<int>> result;
        sort(intervals.begin(), intervals.end(),
             [](const vector<int> &a, const vector<int> &b) {
                 return a[0] < b[0];
             });

        int curStart = intervals[0][0], curEnd = intervals[0][1];
        bool flag = false;
        for (int i = 0; i < n - 1; ++i) {
            if (intervals[i + 1][0] > curEnd) {
                result.push_back({curStart, curEnd});
                curStart = intervals[i + 1][0];
            }
            curEnd = max(curEnd, intervals[i + 1][1]);
        }
        result.push_back({curStart, curEnd});
        return result;
    }
};

AllenY's blog