目录
最⼤数（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀组⾮负整数 nums ，重新排列每个数的顺序（每个数不可拆分）使之组成⼀个最⼤的整数。注意：输出结果可能⾮常⼤，所以你需要返回⼀个字符串⽽不是整数。
⽰例1：
输⼊：nums=[10,2]输出："210"⽰例2：
输⼊：nums=[3,30,34,5,9]输出："9534330"
提⽰：
◦ 1 <= nums.length <= 100
◦ 0 <= nums[i] <= 10(9)
讲解算法原理
解法（贪⼼）：
可以先优化：
将所有的数字当成字符串处理，那么两个数字之间的拼接操作以及⽐较操作就会很⽅便。贪⼼策略：
按照题⽬的要求，重新定义⼀个新的排序规则，然后排序即可。排序规则：
a. 「A拼接B」⼤于「B拼接A」，那么A在前，B在后；b. 「A拼接B」等于「B拼接A」，那么AB的顺序⽆所谓；c. 「A拼接B」⼩于「B拼接A」，那么B在前，A在后；
编写代码
c++算法代码：
class Solution
{
public:
string largestNumber(vector<int>& nums)
{
// 优化：把所有的数转化成字符串
vector<string> strs;
for(int x : nums) strs.push_back(to_string(x));
// 排序
sort(strs.begin(), strs.end(), [](const string& s1, const string& s2)
{
return s1 + s2 > s2 + s1;
});
// 提取结果
string ret;
for(auto& s : strs) ret += s;
if(ret[0] == '0') return "0";
return ret;
}
};java算法代码：
class Solution
{
public String largestNumber(int[] nums)
{
// 优化：把所有的数转化成字符串
int n = nums.length;
String[] strs = new String[n];
for(int i = 0; i < n; i++) strs[i] = "" + nums[i];
// 排序
Arrays.sort(strs, (a, b) ->
{
return (b + a).compareTo(a + b);
});
// 提取结果
StringBuffer ret = new StringBuffer();
for(String s : strs) ret.append(s);
if(ret.charAt(0) == '0') return "0";
return ret.toString();
}
}摆动序列（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第⼀个差（如果存在的话）可能是正数或负数。仅有⼀个元素或者含两个不等元素的序列也视作摆动序列。
• 例如， [1, 7, 4, 9, 2, 5] 是⼀个摆动序列，因为差值 (6, -3, 5, -7, 3) 是正
负交替出现的。
• 相反， [1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第⼀个序列是因为它的
前两个差值都是正数，第⼆个序列是因为它的最后⼀个差值为零。
⼦序列可以通过从原始序列中删除⼀些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你⼀个整数数组 nums ，返回 nums 中作为摆动序列的最⻓⼦序列的⻓度。
⽰例1：
输⼊：nums=[1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为(6,-3,5,-7,3)。⽰例2：
输⼊：nums=[1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含⼏个⻓度为7摆动序列。
其中⼀个是[1,17,10,13,10,16,8]，各元素之间的差值为(16,-7,3,-3,6,-8)。⽰例3：
输⼊：nums=[1,2,3,4,5,6,7,8,9]
输出：2
提⽰：
• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
讲解算法原理
解法（贪⼼）：
贪⼼策略：
对于某⼀个位置来说：
◦ 如果接下来呈现上升趋势的话，我们让其上升到波峰的位置；◦ 如果接下来呈现下降趋势的话，我们让其下降到波⾕的位置。因此，如果把整个数组放在「折线图」中，我们统计出所有的波峰以及波⾕的个数即可。
编写代码
c++算法代码：
class Solution
{
public:
int wiggleMaxLength(vector<int>& nums)
{
int n = nums.size();
if(n < 2) return n;
int ret = 0, left = 0;
for(int i = 0; i < n - 1; i++)
{
int right = nums[i + 1] - nums[i]; // 计算接下来的趋势 if(right == 0) continue; // 如果⽔平，直接跳过
if(right * left <= 0) ret++; // 累加波峰或者波⾕ left = right;
}
return ret + 1;
}
};java算法代码：
class Solution
{
public int wiggleMaxLength(int[] nums)
{
int n = nums.length;
if(n < 2) return n;
int ret = 0, left = 0;
for(int i = 0; i < n - 1; i++)
{
int right = nums[i + 1] - nums[i]; // 计算接下来的趋势 if(right == 0) continue; // 如果⽔平，直接跳过
if(left * right <= 0) ret++; // 累加波峰或者波⾕ left = right;
}
return ret + 1;
}
}