牛牛跳方块题解

牛牛在玩一个跳方块的游戏，他的面前有一片方块区域，由两种颜色的方块组成，一种是红色，一种是黑色。
他每次从起点开始，不断地蓄力跳跃，他需要跳跃到终点。
在每次跳跃中，如果牛牛跳到了黑色方块上，那么他下一步必须向前跳跃，反之，他下一步必须向后跳跃。
他每次可以跳跃的距离为[1,max],max为他单次跳跃的最大距离。
给定一个由'S','E','R','B'组成的的字符串s('R'代表红色，'B'代表黑色,'S'代表起点,'E'代表终点)，返回牛牛单次跳跃时最小的最大距离是多少？

题解:
此题用dfs可能会爆栈，我们可以考虑一个贪心的解法：
假如牛牛跳到了黑色方块上，那么他就可以往前跳跃；
那么假如红色方块在黑色方块的后面，牛牛跳到了红色方块上，那么他只能往回跳跃，
如果他想再次跳到前面的黑色方块上，那么他必须往回跳到后面黑色方块上才行。
那么假如红色方块在黑色方块的前面，牛牛跳到了红色方块上，那么他只能往回跳跃，
如果他想再次跳到前面的黑色方块上，那么他必须往回跳到后面黑色方块上才行。
如上能说明，跳到红色方块其实并没有任何用处，我们只需要判断黑色方块之间的距离即可，即我们只跳黑色方块就可以得到单次跳跃时最小的最大距离。
时间复杂度：
空间复杂度：
参考代码如下：

class Solution {
public:
    /**
     * 给定一个由'S','E','R','B'组成的的字符串s('R'代表红色，'B'代表黑色,'S'代表起点,'E'代表终点)，返回牛牛单次跳跃时最小的最大距离是多少？
     * @param s string字符串 代表题目中的s
     * @return int整型
     */
    int solve(string s)
    {
        // write code here
        int n, i, mx, pre;
        mx = -1;
        n = s.size();
        s[0] = 'B';
        s[n - 1] = 'B';
        pre = 0;
        for (i = 0; i < n; i++)
            if (s[i] == 'B')
            {
                mx = max(mx, i - pre);
                pre = i;
            }
        return mx;
    }
};