最大值

题意

给定一个数字字符串，问其中长度为k的连续数字串最大的值是多少

方法

枚举每个位置作为开头

分析

我们枚举每个起始位置，进行按位比较

过程中记录最大值的起始位置

最后输出结果即可

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    int maxValue(string s, int k) {
        int i0 = 0; // 最大的起始点
        for(int i = 1;i + k < s.length();i++){
            for(int j =0;j<k;j++){
                if(s[i0+j] > s[i+j]) break; // 原来的更大
                if(s[i0+j] < s[i+j]) { // 新的更大
                    i0 = i; // 更新最大起始点
                    break;
                }
            }
        }
        return stoi(s.substr(i0,k)); // 输出
    }
};

复杂度分析

时间复杂度: 对于每个位置，最多比较k位，所以总时间复杂度为$O(kn)O(kn)$

空间复杂度: 只用了常数个额外空间，所以空间复杂度为$O(1)O(1)$

转换+排序

分析

因为长度最大为8，所以直接把所有值提取出来变成数值数组，做排序

输出排序中最大值即可

样例

以样例数据"321",2为例

输出最大的32即可

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    int maxValue(string s, int k) {
        vector<int> vals;
        for(int i = 0;i + k <= s.length();i++){
            vals.push_back(stoi(s.substr(i,k))); // 全部转换成数字
        }
        sort(vals.begin(),vals.end()); // 排序
        return vals.back();
    }
};

复杂度分析

时间复杂度: 主要消耗在转换和排序，所以总时间复杂度为$O(kn+n\cdot log(n))O(kn+n\backslash cdot\; log(n))$

空间复杂度: 主要在转换出的值的保存，所以空间复杂度为$O(n)O(n)$