题解 | #最大值#

最大值

题目描述

有一个只由字符'1'到'9'组成的长度为 n 的字符串 s ，现在可以截取其中一段长度为 k 的子串并且将该子串当作十进制的正整数，如对于子串"123"，其对应的十进制数字就是123 。

如果想让这个正整数尽可能的大的话，问该正整数最大能是多少。

函数传入一个长度为 n 的字符串 s 和一个正整数k，请你返回答案。

方法一：枚举法

解题思路

对于本题目的求解，直接对每个位置进行枚举，并在枚举过程中记录最大值的起始位置，最后得到结果。

解题代码

class Solution {
public:
    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)); // 返回结果
    }
};

复杂度分析

时间复杂度：两层循环，因此时间复杂度为$O(k\ast n)O(k*n)$，其中n为字符串长度，k为题目所给的正整数。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为$O(1)O(1)$

方法二：滑动窗口的方法

解题思路

初始化一个大小为k的区间，然后利用区间，循环右移，计算区间数值，并保存最大值。

解题代码

class Solution {
public:
    int maxValue(string s, int k)
    {
        int len=s.size();
        int res=0,x=0;
        int t=pow(10,k-1);//取余的数
        int r=0;//右指针
        while(r<len)
        {
            if(r<k)
            {//初始化长度为k的区间
                x=x*10+s[r++]-'0';
            }
            else
            {
                res=max(res,x);//维护最大值
                x=x%t;
                x=x*10+s[r++]-'0';
            }
        }
        res=max(res,x);//维护最大值
        return res;//返回结果
    }
};

复杂度分析

时间复杂度：一层循环，因此时间复杂度为$O(n)O(n)$，其中n为字符串长度。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为$O(1)O(1)$。