跳到主要内容

2055.蜡烛之间的盘子

· 阅读需 5 分钟

1、题干​

给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 0 开始的字符串 s ，它只包含字符 '*' 和 '|' ，其中 '*' 表示一个 盘子 ，'|' 表示一支 蜡烛 。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] 表示 子字符串 s[lefti...righti] （包含左右端点的字符）。对于每个查询，你需要找到 子字符串中 在 两支蜡烛之间 的盘子的 数目 。如果一个盘子在 子字符串中 左边和右边 都 至少有一支蜡烛，那么这个盘子满足在 两支蜡烛之间 。

  • 比方说，s = "||**||**|*" ，查询 [3, 8] ，表示的是子字符串 "*||**|" 。子字符串中在两支蜡烛之间的盘子数目为 2 ，子字符串中右边两个盘子在它们左边和右边 都 至少有一支蜡烛。

请你返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。

 

示例 1:

ex-1

输入：s = "**|**|***|", queries = [[2,5],[5,9]]
输出：[2,3]
解释：
- queries[0] 有两个盘子在蜡烛之间。
- queries[1] 有三个盘子在蜡烛之间。

示例 2:

ex-2

输入：s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
输出：[9,0,0,0,0]
解释：
- queries[0] 有 9 个盘子在蜡烛之间。
- 另一个查询没有盘子在蜡烛之间。

 

提示：

  • 3 <= s.length <= 105
  • s 只包含字符 '*' 和 '|' 。
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 0 <= lefti <= righti < s.length

2、解题思路​

按题目意思要查找任意区间 [i,j] 内两支蜡烛之间的盘子数量，要解决两个核心问题：

  • 1、查找区间 [i,j] 内最左边和最右边蜡烛的下标 [l,r]
  • 2、求出区间 [l,r] 内的蜡烛数量

问题1采用区间映射解决，使用二维数组 ranges 存储离任意下标 i 最近的左右蜡烛下标，形如 ranges[i] = [li,ri]。对于任意区间 [i,j] 内最左边和最右边蜡烛的下标为 l = ranges[i][1], r = ranges[j][0]

特殊情况 :

  • 左边没有蜡烛时有 ranges[i] = [-1,ri]
  • 右边没有蜡烛时有 ranges[i] = [li,s.length]
  • 该位置是蜡烛时有 ranges[i] = [i,i]

问题2采用前缀和解决，使用数组 sumList 存储蜡烛数量前缀和，对于任意下标 i 而言 sumList[i] 表示 s[0] 到 s[i] 之间的蜡烛数量。对于任意区间 [l,r] 内的蜡烛数量为 sumList[r] - sumList[l]


至此两个核心问题都得以解决，且都能在 O(1)O(1) 时间复杂度内求出正解


3、代码​

var platesBetweenCandles = function (s, queries) {
    const n = s.length, sumList = new Array(n), ranges = new Array(n);
    let ps = 0, range = [-1, n];

    for (let i = 0; i < n; i++) {
        if (s[i] === '*') {
            ps += 1;
            ranges[i] = range;
        } else {
            range[1] = i;
            ranges[i] = [i, i];
            range = [i, n];
        }

        sumList[i] = ps;
    }

    return queries.map(([i, j]) => {
        const l = ranges[i][1], r = ranges[j][0];
        return l > -1 && r < n && l < r ? sumList[r] - sumList[l] : 0;
    });
};

4、复杂度​

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

5、执行结果​

  • 执行用时: 308 ms
  • 内存消耗: 86.1 MB