算法题，在程序员的面试中非常的常见，想要进大厂，算法能力是必不可少的，今天我们来看一道程序员面试中的算法真题解析。
题目
我们有一个字符串，它是由0-9十个字符组成，我们可以认为它是一个数字，很明显，对于这个字符串中所有的子串，也是一个数字（可能是0开头）。我们定义一个函数f(str)表示这个数字中最小的字符的值。例如f(123)=1。f(523)=2。f(2099)=0。现在给你一个字符串，要求你求出所有的子串的f(str)值之和。
样例输入
1241
样例输出
15
样例解释
1241的字串总共有10个子串，他们分别是（1，2，4，1，12，24，41，124，241，1241）。他们的f(x)值分别是，f(1)=1,f(2)=2,f(4)=4,f(1)=1,f(12)=1,f(24)=2,f(41)=1,f(124)=1,f(241)=1,f(1241)=1,和为15。
解法
想出一个算法来求解这个题目并不难，最简单的，我们想想一想，我们先设计一个找出所有子串的算法。我们可以枚举子串的开始下标，再枚举出子串的结束下标，最后再从这个子串中找出最小值。总共需要枚举3次，算法时间复杂度为O(N^3)。下面是这个算法简单的伪代码：
优化
一些一步到位的算法题，沙茶敏本身并不太喜欢拿出来讲，这种可以逐渐优化的算法题，思考起来才是真的爽。我们不妨来看看下面这种情况，子串2到24，24到241，他们的f(x)有什么联系呢？相信聪明的你已经想到了，只要比较最新的一个字符是不是比上一个结果小即可！即f(sub(i,j)) = min(f(sub(i, j-1)), str[j])。所以，我们就可以优化掉最后一次枚举最小值。把算法时间复杂度优化到O(N^2)。
再一步优化
那么有没有更优秀的解法呢？前面的两种解法，我们都是通过枚举子串，然后来找到最小的值，那么我们能不能换一种思路，枚举最小值，再去寻找那些字符串的最小值是它呢？我们重新举个上述例子，1524321，假如最小的字符是第3位的2，那么它的子串的范围是什么呢。
第3位中的2，然后找到最左边的第一个比2小于等于的2的位置，看到起始的位置有2个选择，往右边找到第一个比2小的值，发现endIndex有2，4，3，2四个不同的选择。总共是2*4=8个不同的组合。
最后的思考
上述的算法有几个值得思考的地方，第3位的2跟第6位的2，是如何避免重复计算呢？一般在计算里面，我们都有左闭右开（或者左开右闭）的小窍门，来避免重复计算。第二是如何去找到最左边跟最右边的位置呢？有没有O(N)的算法呢？这里留给大家去思考。下一章，我们将介绍一个经典的单调性优化方法，尺卷法。有兴趣的话，大家可以进行关注。好了，今天就讲到这里，留点空间给大家思考，下一章，我们再继续讲一讲这个题目的O(N)解法。
