题解 | #最大值#
最大值
http://www.nowcoder.com/practice/c0a95c1c30e94dc190e6acc42cb06930
题意：
有一个只由字符'1'到'9'组成的长度为 n 的字符串 s ，现在可以截取其中一段长度为 k 的子串并且将该子串当作十进制的正整数，如对于子串"123"，其对应的十进制数字就是123 。
如果想让这个正整数尽可能的大的话，问该正整数最大能是多少。
方法一：
暴力枚举
思路：外层循环暴力遍历字符串，枚举起点；
内层循环计算区间长度为 k 的值，并且维护最大值。
class Solution {
public:
int maxValue(string s, int k) {
int len=s.size();
int res=0;
for(int i=0;i<len-k+1;i++){//枚举起点
int x=0;
for(int j=i;j<i+k;j++){//计算长度为k的数
x=x*10+s[j]-'0';
}
res=max(res,x);//维护最大值
}
return res;
}
};
时间复杂度：%2Cn%E6%98%AF%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%95%BF%E5%BA%A6%EF%BC%8Ck%E6%98%AF%E5%8C%BA%E9%97%B4%E5%AD%90%E4%B8%B2%E7%9A%84%E9%95%BF%E5%BA%A6%E3%80%82)
空间复杂度：%2C%E5%B8%B8%E6%95%B0%E7%BA%A7%E5%88%AB%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4%E3%80%82)
方法二：
滑动窗口
思路：首先，初始化长度为 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;
}
};
时间复杂度：%2Cn%E6%98%AF%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%95%BF%E5%BA%A6%EF%BC%8C%E9%81%8D%E5%8E%86%E5%AD%97%E7%AC%A6%E4%B8%B2%E3%80%82)
空间复杂度：
海康威视公司福利 244人发布
