2734.力扣每日一题6/27 Java(贪心算法)_Java

博客主页：音符犹如代码
系列专栏：
关注博主，后期持续更新系列文章
如果有错误感谢请大家批评指出，及时修改
感谢大家点赞👍收藏⭐评论✍

贪心算法

贪心算法（greedy algorithm）是一种在每一步选择中都采取在当前看来是最优的选择，而不考虑整体最优解的算法策略。

贪心算法的基本思想是在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。

贪心算法的优点是简单、高效，通常在一些问题中能够快速得到一个可行的解。但它的缺点也很明显，由于不考虑整体情况，贪心算法得到的解不一定是全局最优解，可能只是局部最优解。

例如，在找零钱问题中，如果要找给顾客 67 元，而手头有面值为 20 元、10 元、5 元、1 元的纸币，贪心算法会每次选择尽可能大面值的纸币，即先选择 3 张 20 元，再选择 1 张 5 元，最后选择 2 张 1 元。这种情况下，贪心算法可以得到最优解。

然而，在一些情况下，贪心算法不能得到最优解。比如在活动选择问题中，如果按照活动结束时间越早优先选择的贪心策略，可能会错过一些更优的组合。

总之，贪心算法适用于一些具有贪心选择性质和最优子结构性质的问题，使用时需要谨慎判断是否能得到全局最优解。

思路

要使字符串在字典序上尽可能小，那么应该尽量把较大的字符删除。首先找到第一个不是 a 的字符位置（因为 a 是最小的字符），如果不存在这样的字符，说明整个字符串都是 a，那么只需将最后一个字符变为 z。如果找到了第一个不是 a 的字符位置，那么从这个位置开始到末尾的字符都可以减 1，这样可以得到一个更小的字典序字符串。

解题方法

代码中使用一个循环遍历字符串，找到第一个不是 a 的字符位置。然后再使用一个循环，将从找到的位置开始到末尾的字符减 1。如果整个字符串都是 a，则直接将最后一个字符变为 z。

时间复杂度

o(n)

空间复杂度

o(1)

code

class solution {
    public string smalleststring(string s) {
        char[] chararray = s.tochararray();
        int start = -1;

        // 找到第一个不是 'a' 的字符位置
        for (int i = 0; i < chararray.length; i++) {
            if (chararray[i]!= 'a') {
                start = i;
                break;
            }
        }

        // 如果没有找到不是 'a' 的字符，直接返回原字符串
        if (start == -1) {
            chararray[chararray.length - 1] = 'z';
            return new string(chararray);
        }

        // 将从找到的位置开始到末尾的字符减 1
        for (int i = start; i < chararray.length; i++) {
            if (chararray[i]!= 'a') {
                chararray[i] = (char) (chararray[i] - 1);
            } else {
                break;
            }
        }

        return new string(chararray);
    }
}