文章目录
- 题目链接
- 题目描述
- 解题思路
- 为什么是贪心
- 一个带图的例子
- 代码
- python
- java
- cpp
- 时空复杂度
- 华为OD算法/大厂面试高频题算法练习冲刺训练
题目链接
LeetCode670、最大交换
题目描述
给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。
设计一个算法使得这 k 个子数组各自和的最大值最小。
示例 1：
输入：nums = [7,2,5,10,8], k = 2
输出：18
解释： 一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
示例 2：
输入：nums = [1,2,3,4,5], k = 2
输出：9
示例 3：
输入：nums = [1,4,4], k = 3
输出：4
提示：
1 <= nums.length <= 10000 <= nums[i] <= 10(6)1 <= k <= min(50, nums.length)
解题思路
数据范围（数字的长度）最大为8，时间复杂度为O(N^3)的暴力法可以通过。
所谓暴力法，就是枚举出所有不同的下标对(i, j)，交换s[i]和s[j]，找到交换完之后最大的那一组。
思路较为简单，故在此略去不表。一下讨论贪心的做法。
为什么是贪心
由于最多只能交换一次，贪心地思考一下这个问题：我们什么希望进行一个怎么样的交换？
换言之，怎么交换才能使得数字尽可能地大？
考虑例子
9091987
原字符串中的第三个"9"是最大且位置尽可能靠后的数字，这个字符应该优先地被交换到尽可能前的位置。由于索引0的数字是"9"，所以考虑索引1的字符"0"和第三个"9"交换。得到答案
9991087
从这个例子可以看出贪心的策略是：
- 首选一个尽可能大的数字（比如示例中选择字符
"9"） - 如果有多个最大的数字，则优先选择位置尽可能靠后的那个（比如示例中选择第三个
"9"） - 将该数字交换到尽可能靠前的位置，即交换到第一个小于该数字的位置（比如示例中索引
1的位置）。
所以考虑逆序遍历原数字字符串（为了方便交换操作，改成数组来操作），并且使用一个栈（类似一个单调栈），储存原数字从右往左看遇到的更大的数字的下标
stack = list()
for i in range(n-1, -1, -1):
if not stack or lst[i] > lst[stack[-1]]:
stack.append(i)
最终这个栈一定会满足以下条件：
- 栈中储存的是原数字字符串的数字的下标
i i的取值自栈底向栈顶递减，即栈顶元素stack[-1]是在数字lst中位置最靠前的下标（满足了上述贪心策略2）lst[i]的取值自栈底向栈顶递增，即栈顶元素对应的下标在数字数组中的取值lst[i]是最大的数字（满足了上述贪心策略1）
以例子num = 9091987为例，栈中的结果是储存了最后三个数字"987"的下标，即stack = [6, 5, 4]
接下来要考虑如何实现上述贪心策略的第三点。
我们可以从头到尾遍历原数字数组lst，将下标i和栈顶元素stack[-1]、以及下标i对应的数字lst[i]和栈顶元素对应的数字lst[stack[-1]]进行比较。若
i < stack[-1]，说明此时下标i的位置位于stack[-1]的左边，可以继续进行后续判断。若lst[i] < lst[stack[-1]]，说明此时可以交换位置i和stack[-1]的两个数字，交换之且退出循环lst[i] >= lst[stack[-1]]，说明此时不能进行交换，i需要继续增大
i >= stack[-1]，说明此时下标i的位置已经不再位于stack[-1]的左边，此时不能再考虑栈顶元素，应该将其弹出
另外，由于涉及弹出操作，如果出现空栈情况，但尚未进行交换，则说明原数字数字本身就是一个非递增序列，需要退出循环。综上，上述贪心操作的代码为
for i in range(n):
if not stack:
break
if i > stack[-1]:
if lst[i] < lst[stack[-1]]:
lst[i], lst[stack[-1]] = lst[stack[-1]], lst[i]
ans = "".join(lst)
break
else:
continue
else:
stack.pop()
一个带图的例子
再举一个例子，num = "9987687676"，答案应该为ans = "9988677676"，可以做出如下图
逆序遍历数组lst，构建栈stack = [8, 7, 4, 1]，为可能进行交换的那些对应较大数字且靠后的位置。
正序遍历i，反复拿出栈顶索引对应的元素lst[stack[-1]]对应的数字和i对应的元素lst[i]进行比较。会经历如下过程。
i < stack[-1]，但lst[i] >= lst[stack[-1]]。不能做交换，i增加。
i >= stack[-1]，即i的位置不位于stack[-1]的左边，stack[-1]出栈，i增加。
i < stack[-1]，但lst[i] >= lst[stack[-1]]。不能做交换，i增加。
i < stack[-1]，且lst[i] < lst[stack[-1]]。进行交换，得到ans = "9988677676"，是可以得到的数字最大的结果。
代码
python
# 贪心+栈：O(N)
class Solution:
def maximumSwap(self, num: int) -> int:
# 用列表的形式储存数字num
lst = list(str(num))
# 获得数字num的位数（即lst的长度）
n = len(lst)
# 构建一个栈，储存原字符串从右往左看遇到的更大数字的下标
stack = list()
# 逆序遍历字符串s
for i in range(n-1, -1, -1):
# 如果栈是空栈，或者当前下标i对应的数字lst[i]大于栈顶下标对应的数字lst[stack[-1]]
# 则将索引i加入stack
if not stack or lst[i] > lst[stack[-1]]:
stack.append(i)
# 正序遍历列表lst
for i in range(n):
# 若出现空栈情况，则退出循环
if not stack:
break
# 如果当前下标i位于栈顶元素stack[-1]的左边
# 则可以进行后续判断
if i < stack[-1]:
# 若当前数字小于栈顶元素对应的数字，则可以进行交换
if lst[i] < lst[stack[-1]]:
lst[i], lst[stack[-1]] = lst[stack[-1]], lst[i]
return int("".join(lst))
# 否则，考虑下一个i，这里的else也可以不写
else:
continue
# 如果当前下标i不位于栈顶元素stack[-1]的左边
# 则弹出栈顶元素，考虑下一个较小但是位于较右位置的数字
else:
stack.pop()
return num
java
public class Solution {
public int maximumSwap(int num) {
char[] chars = Integer.toString(num).toCharArray();
int n = chars.length;
int[] stack = new int[n];
int top = -1;
for (int i = n - 1; i >= 0; i--) {
if (top == -1 || chars[i] > chars[stack[top]]) {
stack[++top] = i;
}
}
for (int i = 0; i < n; i++) {
if (top == -1) {
break;
}
if (i < stack[top]) {
if (chars[i] < chars[stack[top]]) {
char temp = chars[i];
chars[i] = chars[stack[top]];
chars[stack[top]] = temp;
return Integer.parseInt(new String(chars));
}
} else {
top--;
}
}
return num;
}
}
cpp
class Solution {
public:
int maximumSwap(int num) {
std::string numStr = std::to_string(num);
int n = numStr.length();
std::vector<int> stack;
for (int i = n - 1; i >= 0; i--) {
if (stack.empty() || numStr[i] > numStr[stack.back()]) {
stack.push_back(i);
}
}
for (int i = 0; i < n; i++) {
if (stack.empty()) {
break;
}
if (i < stack.back()) {
if (numStr[i] < numStr[stack.back()]) {
std::swap(numStr[i], numStr[stack.back()]);
return std::stoi(numStr);
}
} else {
stack.pop_back();
}
}
return num;
}
};
时空复杂度
时间复杂度：O(N)。仅需一次遍历所有数字。
空间复杂度：O(1)。栈所占空间，最大为9，可视为常数级别空间。
华为OD算法/大厂面试高频题算法练习冲刺训练
-
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！
-
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
-
每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！
-
60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁
-
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
-
可查看链接 大厂真题汇总 & OD真题汇总(持续更新)
-
绿色聊天软件戳
od1336了解更多
