【基础篇 - Day 2】 2023-02-14 - 821. 字符的最短距离 （01. 数组，栈，队列 ）

[threedayAAAAA]

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。

返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。

两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。

 

示例 1：

输入：s = "loveleetcode", c = "e" 输出：[3,2,1,0,1,0,0,1,2,2,1,0] 解释：字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。 距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3 。 距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2 。 对于下标 4 ，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。 距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2 。 示例 2：

输入：s = "aaab", c = "b" 输出：[3,2,1,0]  

提示： 1 <= s.length <= 104 s[i] 和 c 均为小写英文字母 题目数据保证 c 在 s 中至少出现一次

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/shortest-distance-to-a-character 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

方法一

思路

1. 每次遍历判断当前元素是否与要找的字符相同，并且栈不为空，符合则算出之前栈内字符的距离，直到栈空
2. 当前元素与要找的字符相同，直接将距离置为0
3. 当前元素与要找的字符不同，将字符放入栈中
4. 依次循环上面步骤直到数组遍历结束
5. 将栈置为空
6. 反向遍历数组，步骤同上面 1 2 3 4

   1-4 只能算出从左到右的距离 所以需要反向操作一下，算出从右到左的距离，同时取值时进行对比，取较小值即为最优距离

代码

function shortestToChar(s: string, c: string): number[] {
    const sArr = s.split('')
    let indexStack: number[] = []
    const result = new Array(s.length).fill(2000)
    sArr.forEach((item, index) => {
        while(item === c && indexStack.length){
            const targetIndex = indexStack[indexStack.length - 1]
            result[targetIndex] = index - targetIndex
            indexStack.pop()
        }
        if(item === c){
            result[index] = 0
        } else {
            indexStack.push(index)
        }
    })
    indexStack = []
    for(let index = sArr.length - 1; index >= 0; index--){
        while(sArr[index] === c && indexStack.length){
            const targetIndex = indexStack[indexStack.length - 1]
            result[targetIndex] = Math.min(result[targetIndex],  targetIndex - index)
            indexStack.pop()
        }
        if(sArr[index] === c){
            result[index] = 0
        } else {
            indexStack.push(index)
        }
    }
    return result
};

时空复杂度

• 时间复杂度：N + 2 ((1 + 2) N) / 2 = 4 * N ===> O(N)
• 空间复杂度：O(N)

方法二

思路

思路同方法一，只不过我们每次只需要存个变量代表上一次遇到指定字符的index，即可算出当前元素的距离，不需要使用栈

代码

function shortestToChar(s: string, c: string): number[] {
    let preTargetIndex = -2000 
    const result = new Array(s.length).fill(2000)
    for(let index = 0; index < s.length; index++){
        if(s[index] === c){
            preTargetIndex = index
        } 
        result[index] = Math.min(index - preTargetIndex, result[index]) 
    }
    preTargetIndex = 2000
    for(let index = s.length - 1; index >= 0; index--){
        if(s[index] === c){
            preTargetIndex = index
        } 
        result[index] = Math.min(preTargetIndex - index, result[index]) 
    }
    return result
};

时空复杂度

• 时间复杂度：2 * N ===> O(N)
• 空间复杂度：O(1)

[MiumMi]

方案一

思路

暴力求解

1. 先找到元素中所有c字符所在的位置数组 indexArr

2. 遍历元素，每个元素遍历indexArr，找到最小值塞进结果数组中 注：这里可优化一下代码，如每次找到最小值之后，indexArr就可以将j之前的值挪出来了

   代码

   function shortestToChar (s: string, c: string): number[] {
   const len = s.length;
   const indexArr = [];
   const resultArr = [];
   for (let i = 0; i < len; i++) {
   if (s[i] === c) {
     indexArr.push(i);
   }
   }
   const indexLen = indexArr.length;
   for (let i = 0; i < len; i++) {
   let sortData = Math.abs(i - indexArr[0]);
   for (let j = 1; j < indexLen; j++) {
     const value = Math.abs(i - indexArr[j]);
     sortData = value > sortData ? sortData : value;
   }
   resultArr.push(sortData);
   }
   return resultArr;
   }

   ---

   复杂度分析

3. 时间复杂度：O(n*n)

4. 空间复杂度 : O(n)

方案二

思路

1. 初始化两个标识，lastIndex（上一次匹配到的index）, currentIndex(这次匹配到的index)
2. 遍历字符串，如果当前元素不等于字符c,则进待处理栈stack
3. 如果等于字符c，则更新lastIndex和currentIndex标识，并判断待处理栈是否有需要处理的索引，有的话则设置待处理索引的最小距离，最小距离计算时取上一次匹配的值和这一次匹配的值两个的最小值

4. 遍历完所有字符串之后，如果还有待处理索引，则同样进入设置待处理索引的最小距离的逻辑

   代码

   function shortestToChar (s: string, c: string): number[] {
   const len = s.length;
   const stack = [];
   const result = [];
   const max = len * len;
   let currentIndex = max;
   let lastIndex = max;
   
   const setFn = () => {
   let peek = stack.pop();
   const sort = result[peek];
   const nextValue = Math.abs(currentIndex - peek);
   const lastValue = Math.abs(lastIndex - peek);
   const value = nextValue > lastValue ? lastValue : nextValue;
   result[peek] = value > sort ? sort : value;
   }
   
   for (let i = 0; i < len; i++) {
   const isEqual = s[i] === c;
   result[i] = isEqual ? 0 : Math.abs(i - currentIndex);
   if (isEqual) {
     lastIndex = currentIndex;
     currentIndex = i;
   }
   while(stack.length && isEqual) {
     setFn();
   }
   if (!isEqual) {
     stack.push(i);
   }
   }
   
   while(stack.length) {
   setFn();
   }
   
   return result;
   }

   ---

   复杂度分析

5. 时间复杂度：这个不会算，感觉像 n + n? O(n)?

6. 空间复杂度: O(n)

方案三

思路

指针

1. 声明3个标识，lastIndex(上一次匹配到的索引), currentIndex(当前匹配到的索引)，shortIndex(已经计算完最小距离的索引 +1)

2. 如果当前元素等于字符，则更新lastIndex和currentIndex标识，遍历shortIndex到currentIndex，计算每个索引的最小值（最小距离计算时取上一次匹配的值和这一次匹配的值两个的最小值），更新shortIndex

   代码

   function shortestToChar (s: string, c: string): number[] {
   const len = s.length;
   const max = len * len;
   let currentIndex = max;
   let lastIndex = max;
   let shortIndex = 0;
   let result = new Array(len).fill(-1);
   for (let i = 0; i < len; i++) {
   result[i] = Math.abs(i - currentIndex);
   if (s[i] === c) {
     lastIndex = currentIndex;
     currentIndex = i;
     for(let j = shortIndex; j <= currentIndex; j++) {
       const value = Math.abs(j - currentIndex);
       const lastValue = Math.abs(j - lastIndex);
       result[j] = lastValue > value ? value : lastValue; 
     }
     shortIndex = i + 1;
   }
   }
   return result;
   }

   ---

   复杂度分析

3. 时间复杂度：这个也不会算

4. 空间复杂度: O(1)

[yunliuyan]

思路

• 队列解法，将字符串开始遍历，对应的下标开始入栈，
• 当入栈的字符与c相等，则将栈里面的值都出栈，
• 如果是第一次用栈，则直接取栈下标反元素存入结果数组中去，并将出现的c的下标存到缓存变量中
• 如果是第二次以后，则记录栈里的值减去上一个出现c的下标值，与现在出现的下标值减去栈里的值，取最小
• 如果没有了c，但栈里面还有元素，直接用栈里的值减去上一次c的下标值

代码

function shortestToChar(s: string, c: string): number[] {
    const result: number[] = [];
    let stack: number[] = [];
    let preCIndex = -1;
    for(let i = 0; i < s.length; i++) {
        stack.push(i);
        if(s[i] === c) {
            for(let j = 0; j < stack.length; j++ ) {
                result.push(
                    preCIndex === -1 ? stack.length - j - 1 :
                    Math.min(stack[stack.length - 1] - stack[j], stack[j] - preCIndex));
            }
            preCIndex = i;
            stack = [];
        }
    }
    if (stack.length) {
        for(let j = 0; j < stack.length; j++ ) {
            result.push(stack[j] - preCIndex);
        }
    }
    return result;
};

复杂度分析

• 时间复杂度 O(n)
• 空间复杂度 O(n)