题解 | #最大值#

题意整理

给定一个只由字符'1'到'9'组成的长度为n的字符串s。
求s的长度为k的子串中，对应的最大的十进制数值。

方法一（字符串截取）

1.解题思路

遍历整个字符串，每次截取当前长度为k的子串。
计算子串对应的十进制数值，取最大的一个。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    public int maxValue (String s, int k) {
        //字符串长度
        int n=s.length();
        int res=0;
        for(int i=0;i<=n-k;i++){
            //获取当前k位子串对应的数值
            Integer num=Integer.parseInt(s.substring(i,i+k));
            //得到最大值
            res=Math.max(res,num);
        }
        return res;
    }
}

3.复杂度分析

时间复杂度：最多遍历整个字符串一次，每次截取的时间复杂度为O(k)，所以时间复杂度是 $O (n * k)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O (1)$ 。

方法二（滑动窗口）

1.解题思路

首先计算第一个长度为k的子串对应的十进制数值，以及对应位数的变化。
然后遍历整个子串，每次当过位数值得到移除最高位之后的数值，从而快速计算出下一个长度为k的子串对应的十进制数组。通过这种方式，可以得到所有长度为k的子串对应的十进制数值。取所有数值中的最大值即可。

图解展示： alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    public int maxValue (String s, int k) {
        int n=s.length();
        int max=0,num=0;
        //位数
        int digit=1;
        //第一个长度为k的子串，计算其对应的数值
        for(int i=0;i<k;i++){
            num=num*10+s.charAt(i)-'0';
            digit*=10;
        }
        
        //初始化为num
        max=num;
        for(int i=k;i<n;i++){
            //移除最高位，剩下的数值
            num%=digit/10;
            //当前k位子串对应的数值
            num=num*10+s.charAt(i)-'0';
            //取较大值
            max=Math.max(max,num);
        }
        return max;
    }
}

3.复杂度分析

时间复杂度：最多遍历整个字符串一次，所以时间复杂度是 $O (n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O (1)$ 。