[动态规划]leetcode821：字符的最短距离

题目：

题解：

思路：类比接雨水，两次遍历求解最佳答案。

代码如下：

class Solution {
public:
    // 思路：类比接雨水，两次遍历求距离的最小值
    vector<int> shortestToChar(string s, char c) {
        int n=s.size();
        vector<int> res(n,0);
        // 正向遍历：s[i]左边最近的c字符到位置i之间的距离，idx记录s[i]左边字符c出现的上一个位置
        for(int i=0,idx=-n;i<n;++i){
            if(s[i]==c){
                idx=i;
            }
            res[i]=i-idx;
        }
        // 反向遍历：s[i]右边最近的c字符到位置i之间的距离，idx记录s[i]右边字符c出现的上一个位置
        for(int i=n-1,idx=2*n;i>=0;--i){
            if(s[i]==c){
                idx=i;
            }
            res[i]=min(res[i],idx-i);
        }
        return res;
    }
};