【算法】贪心算法

贪心算法也是最常用的算法之一，很多困难问题使用贪心算法会大幅简化。贪心算法的思想很简单，贪心算法每一次都做出当前看起来最好的选择，而不用考虑其它可能的选择。

贪心算法的学习可以与动态规划算法进行比较，看看它到底比动态规划算法少考虑了哪些子问题，为什么可以少考虑那些子问题，而每次只专注于求解一个子问题，通过逐步递推得到原问题的答案。

一般来说，使用贪心算法也需要满足一定的条件：

• 最优子结构：规模较大的问题的解由规模较小的子问题的解组成，区别于「动态规划」，可以使用「贪心算法」的问题「规模较大的问题的解」只由其中一个「规模较小的子问题的解」决定；
• 无后效性：后面阶段的求解不会修改前面阶段已经计算好的结果；
• 贪心选择性质：从局部最优解可以得到全局最优解。

回顾动态规划解决问题时需要满足的条件，贪心算法多了一条贪心选择性质，因此一般来说能用贪心的题目都可以用动态规划解决，但能用动态规划的题目不一定能用贪心解决。

1 最简单的贪心

首先通过一道最经典的贪心问题理解贪心算法的思路。

分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

解决这道问题的核心思想是，从最小胃口的孩子开始满足，如果连最小的胃口的孩子都满足不了，那么更大胃口的孩子也无法满足，因此对于每一个孩子，找到大于他的胃口值的最小饼干分发给他即可。所以对两个数组排序然后双指针分发饼干即可。

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int cnt = 0;
        for(int i = 0, j = 0; i < g.size() && j < s.size(); ++i, ++j)
        {
            while(j < s.size() && g[i] > s[j]) ++j;
            if(j < s.size()) ++cnt;
        }
        return cnt;
    }
};

这是最简单的贪心思想，至于为什么能这么做，我们甚至不需要证明也能想明白，当然也可以在官方题解中找到严格的证明。但对于一些困难的问题，有时不通过严谨的证明我们无法想清楚为什么可以使用贪心，也因此想不到用贪心算法去解决。所以贪心算法最困难的地方在于如何证明能够通过局部最优解得出全局最优解。

贪心算法几乎没有套路，到底如何贪心，贪什么与我们要解决的问题密切相关。因此学习贪心算法需要多做多练，然后才有直觉，猜测一个问题可能需要使用贪心算法，进而尝试证明，学会证明。

2 找零钱问题

可以使用贪心算法解决的一类经典问题是找零钱问题。在生活中，我们找给别人零钱，通常都是按照先给出尽可能多的面值较大的纸币（硬币），然后再给出尽可能多的面值第二大的纸币（硬币），直到凑成了我们需要凑出的金额为止，这样找零钱得到的纸币（硬币）的张数（个数）最少。

柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

由于只有三种面值，对于每一种面值有如下结论：

• 如果顾客支付 5 美元，则无需找零，直接收下
• 如果顾客支付 10 美元，需要找零 5 美元，如果没有 5 美元则返回 false
• 如果顾客支付 20 美元，需要找零 15 美元，这时有两种情况，找零 1 张 10 美元和 1 张 5 美元，或者找零 3 张 5 美元，如果能够满足第一种情况，那我们优先按第一种方式找零，因为要尽可能保留 5 美元，5 美元在找零上需要的场合比 10 美元更多

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0;
        for(int b : bills)
        {
            if(b == 5) ++five;
            else if(b == 10){
                if(five > 0) --five, ++ten;
                else return false;
            }
            else{
                if(ten > 0 && five > 0) --ten, --five;
                else if(five > 2) five -= 3;
                else return false;
            }
        }
        return true;
    }
};

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

这道题不能使用贪心算法，因为不满足贪心选择性质，如果每次我们都选择面值最大的硬币去凑成 amount，那么有可能存在使用较小面值的硬币组合可以成 amount，但是用较大面值的硬币无法凑成 amount 的情况，因此不能使用贪心算法。但是显然这道题满足最优子结构和无后效性，因此可以使用动态规划解决。

定义状态 dp[amount] 表示凑成 amount 所需的最少硬币数，边界条件显然是 dp[0] = 0，对于每一个amount，都可以选择任意一个硬币，如果选择硬币 c ，则 dp[amount] = dp[amount - c] + 1，遍历所有 c ，取最小值即可，注意前提是 amount 要比 c 大。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for(int i = 1; i <= amount; ++i)
        {
            for(int c : coins)
            {
                if(i >= c && dp[i-c] != INT_MAX) dp[i] = min(dp[i], dp[i-c] + 1);
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

3 区域选择问题

有一类使用贪心算法解决的问题称为活动选择问题，解决这一类问题的核心思路是优先选择最早的活动。

无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回需要移除区间的最小数量，使剩余区间互不重叠 。

问题等价于寻找数量最多的互不重叠的子区间。使用动态规划很简单，按左端点排序，问题就变成了最长上升子序列问题：

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        sort(intervals.begin(), intervals.end());
        vector<int> dp(n, 1);
        for(int i = 1; i < n; ++i)
        {
            for(int j = 0; j < i; ++j)
            {
                if(intervals[j][1] <= intervals[i][0]) dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        return n - dp[n-1];
    }
};

动态规划的时间复杂度是 O(nlogn)，使用贪心法可以优化到 O(n)。我们按照区间右端点排序，然后遍历所有区间考虑下一步选择哪个区间。因为是按照区间右端点排序的，所以后面的区间右端点一定比当前区间右端点大，如果两个区间右端点相等，选择哪个区间都可以，对下一步区间选择不会产生影响，对最终结果也不会产生影响，所以只需要考虑左端点。如果下一个区间的左端点小于等于当前区间的右端点，说明两个区间不重叠，于是就选择这个区间作为下一个区间。这样只需要遍历一次数组就可以得出最多的不重叠的子区间数量。

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        sort(intervals.begin(), intervals.end(), [](auto& x, auto& y)
        {
            return x[1] < y[1];
        });
        int cnt = 1, right = intervals[0][1];
        for(int i = 1; i < n; ++i)
        {
            if(intervals[i][0] >= right)
            {
                ++cnt;
                right = intervals[i][1];
            }
        }
        return n - cnt;
    }
};

用最少数量的箭引爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆 。可以射出的弓箭的数量没有限制 。 弓箭一旦被射出之后，可以无限地前进。给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数 。

和上一题相反，这道题实际上是在找重叠子区间，并且要使重叠的子区间尽可能多，我们依然按照区间右端点排序，每次我们从右端点最小的区间射出一只箭，因为至少要保证当前所有气球中右端点最小的气球也得被引爆，然后向后扫描判断哪些气球会被引爆，显然与当前区间重叠的区间就会被引爆。如果一个区间左端点比当前区间右端点小，说明区间重叠会被引爆，直到区间的左端点比当前区间右端点大，说明与当前区间重叠的气球都被引爆了，这时这个区间作为就是右端点最小的区间，从这个区间的右端点射出一之箭继续判断，这样最终能够保证射出的箭最少，也就是每次重叠的子区间最多。官方题解给出了生动的图描述这一过程。

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](auto& x, auto& y)
        {
            return x[1] < y[1];
        });
        int ans = 1, right = points[0][1];
        for(int i = 1; i < points.size(); ++i)
        {
            if(points[i][0] > right)
            {
                ++ans;
                right = points[i][1];
            }
        }
        return ans;
    }
};

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

按照左端点排序即可。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        sort(intervals.begin(), intervals.end(), [](auto& x, auto& y)
        {
            return x[0] < y[0];
        });
        int left = intervals[0][0], right = intervals[0][1];
        for(int i = 1; i < intervals.size(); ++i)
        {
            if(intervals[i][0] <= right)
            {
                right = max(right, intervals[i][1]);
                left = min(left, intervals[i][0]);
            }
            else
            {
                ans.push_back({left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        ans.push_back({left, right});
        return ans;
    }
};

4 跳跃问题

跳跃问题也是使用贪心算法解决的经典问题。

跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

因为每个位置之间的间隔为 1 ，因此在当前位置 i 能到达的最远距离为 i + nums[i]，我们维护一个能达到的最远距离，然后对于每个位置判断能否到达，如果可以到达更新最远距离，如果最远距离比数组的最后一个位置远，直接返回 true即可。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        if(n < 2) return true;
        int farest = nums[0];
        for(int i = 1; i < n; ++i)
        {
            if(farest >= n - 1) return true;
            else if(farest >= i) farest = max(farest, i + nums[i]);
        }
        return false;
    }
};

跳跃游戏 II

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。假设你总是可以到达数组的最后一个位置。你的目标是使用最少的跳跃次数到达数组的最后一个位置。输出最少跳跃次数。

核心思想是每次都跳跃都保证下一次跳跃能到达的最远距离最大，因此我们维护当前跳远所能到达的最远距离，在这个范围内不断更新下一次跳跃所能到达的最远距离，当到达这次跳跃的边界的时候，更新下一次跳跃的边界，并且步数加一，相当于跳到了下一次跳跃能到达最远距离的位置。更详细的思路解释可以查看题解。

class Solution {
public:
    int jump(vector<int>& nums) {
        int maxPos = 0, n = nums.size(), end = 0, step = 0;
        for (int i = 0; i < n - 1; ++i) {
            maxPos = max(maxPos, i + nums[i]);
            if (i == end) {
                end = maxPos;
                ++step;
            }
        }
        return step;
    }
};

5 其他简单贪心问题

判断子序列

买卖股票的最佳时机 II

数组拆分 I

卡车上的最大单元数

玩筹码

交换字符使得字符串相同

有两个长度相同的字符串 s1 和 s2，且它们其中只含有 字符 “x” 和 “y”，你需要通过「交换字符」的方式使这两个字符串相同。

每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换 s1[i] 和 s2[j]，但不能交换 s1[i] 和 s1[j]。

最后，请你返回使 s1 和 s2 相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回 -1 。

统计 x 和 y 的个数，如果个数有奇数一定无法相同，同时统计 s1 中为 x ，s2 中为 y 的个数记为 xy， s1 中为 y ，s2 中为 x 的个数记为 yx，根据示例可以看出，两对 xy 或者两对 yx 需要交换一次变为相同， 一对 xy 和 一对 yx 需要两次交换变为相同，因此统计完之后尽量先用相同的 xy 和 yx 交换，就可以保证交换次数最少。

class Solution {
public:
    int minimumSwap(string s1, string s2) {
        if(s1.size() != s2.size()) return -1;
        int x = 0, y = 0, xy = 0, yx = 0;
        for(int i = 0; i < s1.size(); ++i)
        {
            if(s1[i] == 'x' && s2[i] == 'x') x += 2;
            if(s1[i] == 'y' && s2[i] == 'y') y += 2;
            if(s1[i] == 'x' && s2[i] == 'y') ++xy, ++x, ++y;
            else if(s1[i] == 'y' && s2[i] == 'x') ++yx, ++x, ++y;
        }
        if(x % 2 != 0 || y % 2 != 0) return -1;
        return xy / 2 + yx / 2 + (xy % 2) * 2;
    }
};

构造 K 个回文字符串

给你一个字符串 s 和一个整数 k 。请你用 s 字符串中所有字符构造 k 个非空回文串 。

如果你可以用 s 中所有字符构造 k 个回文字符串，那么请你返回 True ，否则返回 False 。

考虑整个字符串中能构建的最少的回文串个数和最多的回文串个数，如果 k 在这之间就返回 true。

最多的回文串个数就是 s 的长度，最少的回文串个数需要一定的思考。

注意到回文串只有两种情况，一种是以一个字母为回文中心，这样的回文串只有一个字母出现奇数次，其余字母都出现偶数次；另一种是以两个相同字母作为回文中心，这样的回文串所有字母都出现偶数次。因此统计 s 中出现奇数次和偶数次字母的个数，能构建的最少的回文串个数就是出现奇数次字母的个数。

class Solution {
public:
    bool canConstruct(string s, int k) {
        if(s.size() < k) return false;
        unordered_map<char, int> map;
        for(auto c : s)
        {
            ++map[c];
        }
        int odd = 0;
        for(auto k : map)
        {
            if(k.second % 2 != 0) ++odd;
        }
        if(k >= odd && k <= s.size()) return true;
        return false;
    }
};

使括号有效的最少添加

返回为使括号字符串 s 有效而必须添加的最少括号数。s 只包含 '(' 和 ')' 字符。

使用栈非常简单，如何使用常数空间解决？

记录一个平衡度 bal， 遇到左括号平衡度加 1，遇到右括号平衡度 - 1，平衡度为 0 说明括号全部匹配，如果平衡度为 -1， 说明需要在前面补一个左括号，如果平衡度大于 0 ，说明需要在后面补若干个右括号。

class Solution {
public:
    int minAddToMakeValid(string s) {
        int ans = 0, bal = 0;
        for (int i = 0; i < s.size(); ++i) {
            bal += s[i] == '(' ? 1 : -1;
            if (bal == -1) {
                ans++;
                bal++;
            }
        }
        return ans + bal;
    }
};

两地调度

公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCosti, bCosti] 。第 i 人飞往 a 市的费用为 aCosti ，飞往 b 市的费用为 bCosti 。返回将每个人都飞到 a 、b 中某座城市的最低费用，要求每个城市都有 n 人抵达。

一般这种问题显然可以用贪心算法，而且问题的关键都是如何排序，也就是按什么值进行排序。

假设让所有人都先飞往 b 市，然后改变一部分人的行程使其飞往 a 市，这时要付出的代价是这部分人 costa - costb 的总和，使这部分代价最小就可以使总代价最小，因此按照 aCosti - bCosti 排序。

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(costs.begin(), costs.end(), [](auto& x, auto& y)
        {
            return x[0] - x[1] < y[0] - y[1];
        });
        int ans = 0;
        for(int i = 0; i < costs.size(); ++i)
        {
            if(i < costs.size() >> 1) ans += costs[i][0];
            else ans += costs[i][1];
        }
        return ans;
    }
};

给定行和列的和求可行矩阵

给你两个非负整数数组 rowSum 和 colSum ，其中 rowSum[i] 是二维矩阵中第 i 行元素的和， colSum[j] 是第 j 列元素的和。换言之你不知道矩阵里的每个元素，但是你知道每一行和每一列的和。

请找到大小为 rowSum.length x colSum.length 的任意非负整数矩阵，且该矩阵满足 rowSum 和 colSum 的要求。请你返回任意一个满足题目要求的二维矩阵，题目保证存在至少一个可行矩阵。

关键在于题目保证一定存在满足条件的矩阵，因此 sum(rowSum) == sum(colSum)。所以对于位置 [i, j]，我们把第 i 行的和与第 j 列的和中的最小值填进去，然后更新第 i 行的和与第 j 列的和，这样永远可以保证 sum(rowSum) == sum(colSum)，因此这样填下去最后一定能找到满足条件的矩阵。

class Solution {
public:
    vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
        int m = rowSum.size(), n = colSum.size();
        vector<vector<int>> ans(m, vector<int>(n));
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                ans[i][j] = min(rowSum[i], colSum[j]);
                rowSum[i] -= ans[i][j];
                colSum[j] -= ans[i][j];
            }
        }
        return ans;
    }
};

6 其他进阶贪心问题

分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果
• 相邻两个孩子评分更高的孩子会获得更多的糖果

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

按照题目要求，每个孩子的糖果数量要满足两个条件：

• 如果这个孩子评分高，那么他的糖果数量要比左边的孩子多
• 如果这个孩子评分高，那么他的糖果数量要比右边的孩子多

因此我们可以维护一个数组 candy 存储每个孩子的糖果数量，先给每个孩子 1 个糖果，然后从左到右遍历，保证每个分数高的孩子都比他左边的孩子糖果数量多，因此如果 ratings [i] > ratings [i-1]，那么 candy[i] = candy[i-1] + 1；然后再从右到左遍历使得每个孩子都满足第二个条件，也就是说如果当前孩子比他右边的孩子评分高，但是糖果数却没有右边的孩子多，即 ratings [i] > ratings [i+1] && candy[i] <= candy[i+1]，那么 candy[i] = candy[i+1] + 1。

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size(), res = 0;;
        vector<int> candy(n, 1);
        //第一次遍历保证分数高的孩子比左边的孩子糖果多
        for(int i = 1; i < n; ++i)
        {
            if(ratings[i-1] < ratings[i]) candy[i] = candy[i-1] + 1;
        }
        //第二次遍历保证分数高的孩子比右边的孩子糖果多
        for(int i = n - 2; i >= 0; --i)
        {
            if(ratings[i] > ratings[i+1] && candy[i] <= candy[i+1]) candy[i] = candy[i+1] + 1;
        }
        return accumulate(candy.begin(), candy.end(), 0);
    }
};

对于这道题，官方题解给出了更巧妙的常数空间遍历方法。

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

之前用动态规划做过，这道题用贪心也很简单，如果当前的连续子数组和 sum 小于 0，则直接置 0，为了防止数组全是负数的情况，我们先计算到目前为止的连续子数组和，并更新答案，最后再判断是否小于 0.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0, ans = INT_MIN;
        for (int num : nums) {
            sum += num;
            ans = max(ans, sum);
            if (sum < 0) sum = 0;
        }
        return ans;
    }
};

摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。给你一个整数数组 nums ，返回 nums 中作为摆动序列的最长子序列的长度 。

显然想到用动态规划，对于每个数字 nums[i] 有下面两种情况：

• 如果 nums[i] - nums[i-1] > 0，那么以 nums[i] 结尾的最长摆动子序列长度有两种可能的情况：
  • nums[i-1] - nums[i-2] > 0，说明连续的两对数的差值都大于 0，此时 nums[i]无作用，以 nums[i] 结尾的最长摆动子序列长度就等于以 nums[i-1] 结尾的最长摆动子序列长度
  • nums[i-1] - nums[i-2] < 0，说明这三个数可以构成摆动序列，此时以 nums[i] 结尾的最长摆动子序列长度等于以 nums[i-1] 结尾的最长摆动子序列长度加 1
• 如果 nums[i] - nums[i-1] < 0，推导同上
• 如果 nums[i] - nums[i-1] = 0，说明两数相等，此时 nums[i]无作用，以 nums[i] 结尾的最长摆动子序列长度就等于以 nums[i-1] 结尾的最长摆动子序列长度

因此我们定义状态 dp[i][j] （j = 0 或 1）表示以 nums[i] 结尾的最长摆动子序列长度，j = 0 时表示nums[i] - nums[i-1] > 0，j = 1 时表示 nums[i] - nums[i-1] < 0 ，根据上面的推导我们可以写出状态转移方程：

if(nums[i] - nums[i-1] > 0) dp[i][0] = max(dp[i-1][0], dp[i-1][1] + 1);
if(nums[i] - nums[i-1] < 0) dp[i][1] = max(dp[i-1][1], dp[i-1][0] + 1);
if(nums[i] - nums[i-1] == 0) dp[i][0] = dp[i-1][0], dp[i][1] = dp[i-1][1];

边界条件是只有一个数时也是摆动序列，因此 dp[0][0] = dp[0][1] = 1。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = dp[0][1] = 1;
        for(int i = 1; i < n; ++i)
        {
            if(nums[i] - nums[i-1] > 0) dp[i][0] = max(dp[i-1][0], dp[i-1][1] + 1);
            else if(nums[i] - nums[i-1] < 0) dp[i][1] = max(dp[i-1][1], dp[i-1][0] + 1);
            else dp[i][0] = dp[i-1][0], dp[i][1] = dp[i-1][1];
        }
        return max(dp[n-1][0], dp[n-1][1]);
    }
};

显然状态 i 只与状态 i - 1 有关，因此可以只用两个数 pos 和 neg 表示状态：

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        int pos = 1, neg = 1;
        for(int i = 1; i < n; ++i)
        {
            if(nums[i] - nums[i-1] > 0) pos = max(pos, neg + 1);
            else if(nums[i] - nums[i-1] < 0) neg = max(neg, pos + 1);
        }
        return max(pos, neg);
    }
};

这道题的贪心方法也比较容易想到，我们只要从左到右扫描数组，同时记录相邻两个数之间的差值，然后每次的差值和上一次的差值判断是否异号，只要异号就可以构成摆动序列，因此长度加 1 ，对于特殊情况如果两数差值为 0，则当前数字无用，记录的差值不能改变为0 ，依然记录之前的差值即可。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if(n < 2) return 1;
        int flag = 0, ans = 1;	//初始化时差值设置为0，序列长度设置为1，相当于直接取第一个数
        for(int i = 1; i < n; ++i)
        {
            //判断flag时用 <= 和 >= 
            //这是因为无论第二个数和第一个的差值如何，都可以取第二个数，除非二者差值也为0
            if(nums[i] - nums[i-1] > 0 && flag <= 0) ++ans;
            else if(nums[i] - nums[i-1] < 0 && flag >= 0) ++ans;
            else continue;
            flag = nums[i] - nums[i-1];
        }
        return ans;
    }
};

单调递增的数字

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回小于或等于 n 的最大数字，且数字呈单调递增 。

我们可以从左到右扫描数字的每一位，如果遇到不递增的位 n[i] 使得 n[i] > n[i-1]，此时可以让 n[i-1] - 1，然后 n[i] 及之后的所有位都设为 9 即可得到小于 n 的最大单调递增数字。需要处理的重点是 n[i-1] - 1 后可能会使前面已经扫描过的位不满足单调递增关系，因此我们再从 n[i-1] 向前扫描找到不会影响单调递增的最后一位，使其减去 1，再把之后的所有位设置为 9 即可。

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string nums = to_string(n);
        for(int i = 1; i < nums.size(); ++i)
        {
            if(nums[i] < nums[i-1])
            {
                int j = i - 1;
                while(j > 0 && nums[j] - 1 < nums[j - 1])
                {
                    --j;
                }
                --nums[j];
                for(int k = j + 1; k < nums.size(); ++k) nums[k] = '9';
                break;
            }
        }
        return stoi(nums);
    }
};

移掉 K 位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

贪心的思考这道题，实际上只需要在原字符串中找到 num.size() - k 个最小的数字组成新的数字，并且数字的顺序不改变即可，显然可以用单调栈解决。为了减少开销，我们用双端队列代替栈，这样可以方便最后组成答案，否则还要倒序插入每个数字。关于前导 0 的处理，官方题解使用一个 bool 类型去处理，我们也可以使用 c++ 字符串自带的方法找到字符串中第一个不为 0 的位置。

class Solution {
public:
    string removeKdigits(string num, int k) {
        int n = num.size();
        if(k >= n) return "0";
        vector<char> s;
        for(char x : num)
        {
            while(!s.empty() && s.back() > x && k > 0)
            {
                s.pop_back();
                --k;
            }
            s.push_back(x);
        }
        while(k > 0)
        {
            s.pop_back();
            --k;
        }
        string ans = "";
        for(char x : s) ans += x;
        int pos = ans.find_first_not_of('0');
        return pos == string::npos ? "0" : ans.substr(pos, ans.size());
    }
};

翻转矩阵后的得分

有一个二维矩阵 A ，其中每个元素的值为 0 或 1 。

移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。

在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。返回尽可能高的分数。

这道题比较困难。因为通过分析题意我们需要掌握两个重要的认识，而这都是不容易想到的：

• 给定一个翻转方案，则它们之间任意交换顺序后，得到的结果保持不变。因此，我们总可以先考虑所有的行翻转，再考虑所有的列翻转。
• 为了得到最高的分数，矩阵的每一行的最左边的数都必须为 1。

因此我们先把所有最左边的数不为 1 的行进行翻转，然后开始进行列翻转，列翻转只要保证每一列的 1 数量更多即可保证最终所有行的数字总和最大。因此从第二列开始，计算这一列中 0 的个数和 1 的个数，如果 0 多则翻转这一列，如果 1 多则无需翻转。

实际编码时我们不需要模拟这个过程，只要按列计算对总和的贡献即可。第一列如果是 1 ，那么对总和的贡献就是 $2^{n-1}$，因为第一列全为 1 ，因此总贡献为 $m·2^{n-1}$，之后第 $j$ 列如果为 1 ，则贡献为 $2^{n-j-1}$，我们统计第 $j$ 列 0 的个数和 1 的个数，个数更多的作为最终的 1 的个数 k，那么这一列的总贡献即为 $k·2^{n-j-1}$。

另外需要注意的是，每一列在统计个数时要考虑行翻转的情况，我们要判断每行做左边的数是否为 1 ，如果为 1 说明这行没有进行翻转，如果不为 1 说明这行经过了翻转，因此该行中每个元素 x 的实际取值应该是 1 - x。

class Solution {
public:
    int matrixScore(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = m * (1 << (n - 1));
        for (int j = 1; j < n; j++) {
            int nOnes = 0;
            for (int i = 0; i < m; i++) {
                if (grid[i][0] == 1) {  //当前行首元素为1，无需翻转
                    nOnes += grid[i][j];
                } else {    //说明这一行进行了翻转，因此该行每个数字的取值为1-x
                    nOnes += (1 - grid[i][j]); 
                }
            }
            int k = max(nOnes, m - nOnes);
            ans += k * (1 << (n - j - 1));
        }
        return ans;
    }
};