每日leetcode第0012天 0670. Maximum Swap

这是一道看上去很简单,实际上不简单的题目。

这里用到了贪心算法。

直觉说我们要想尽量让前面的数字变成最大的数字。

但有可能前面的数字已经是最大了,就要往后推。

交换的可能就不是最大的数字,而是较大的数字了。

并且较大的数字在尾部可能出现了多个,我们应该选择最后的那个,这样损失会最小。

1.遍历找到每种数字最后出现的索引号。

2.从左往右搜索,如果较大的数字的索引号在靠后位置则交换。这里较大数字从9开始尝试。

很巧妙的一步是如果没有这种数字的话,最后出现索引号为0,所以也就不满足if语句无法交换。

在最后不要忘记倘若没有交换也要输出结果。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

每日leetcode第0012天 0670. Maximum Swap》有2条回应

  1. ojbk说:

    那么简单的题目,为什么要写得那么复杂?把最大数字找到换到第一位不就好了?

发表评论

您的电子邮箱地址不会被公开。