leetcode
leetcode 1801 ~ 1850
蜡烛之间的盘子

蜡烛之间的盘子

难度:

标签:

题目描述

给你一个长桌子,桌子上盘子和蜡烛排成一列。给你一个下标从 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

代码结果

运行时间: 164 ms, 内存: 47.7 MB


// 思路:使用Java Stream API进行处理,我们可以通过stream的方式进行字符串的处理和数据的计算,但考虑到效率问题,主要逻辑不变。

import java.util.Arrays;

public int[] platesBetweenCandles(String s, int[][] queries) {
    int n = s.length();
    int[] leftCandle = new int[n];
    int[] rightCandle = new int[n];
    int[] platesCount = new int[n];
    int[] result = new int[queries.length];

    Arrays.fill(leftCandle, -1);
    Arrays.fill(rightCandle, -1);

    // Finding leftmost candles
    Arrays.stream(s.split(""))
          .forEachIndexed((i, c) -> {
              if (c.equals("|")) {
                  leftCandle[i] = i;
              } else if (i > 0) {
                  leftCandle[i] = leftCandle[i - 1];
              }
          });

    // Finding rightmost candles
    Arrays.stream(s.split(""))
          .collect(Collectors.toCollection(LinkedList::new))
          .descendingIterator()
          .forEachRemaining((c, i) -> {
              if (c.equals("|")) {
                  rightCandle[i] = i;
              } else if (i < n - 1) {
                  rightCandle[i] = rightCandle[i + 1];
              }
          });

    // Counting plates
    Arrays.stream(s.split(""))
          .forEachIndexed((i, c) -> {
              if (c.equals("*")) {
                  platesCount[i] = platesCount[i - 1] + 1;
              } else if (i > 0) {
                  platesCount[i] = platesCount[i - 1];
              }
          });

    // Calculating results
    for (int i = 0; i < queries.length; i++) {
        int leftIndex = rightCandle[queries[i][0]];
        int rightIndex = leftCandle[queries[i][1]];
        if (leftIndex != -1 && rightIndex != -1 && leftIndex <= rightIndex) {
            result[i] = platesCount[rightIndex] - platesCount[leftIndex];
        }
    }

    return result;
}

解释

方法:

此题解采用了预处理数组的方法来优化查询。首先,使用前缀和数组 preSum 来记录从字符串开头到当前位置的盘子数量。其次,使用两个数组 left 和 right 分别存储每个位置左侧最近的蜡烛位置和右侧最近的蜡烛位置。通过这种方式,对于每一个查询,可以快速找到查询范围内左侧和右侧的第一个蜡烛,并计算这两个蜡烛之间的盘子数量。

时间复杂度:

O(n + q)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么需要使用前缀和数组来记录盘子的数量?直接在处理查询时统计不可以吗?
使用前缀和数组记录盘子的数量可以大大优化性能。如果直接在处理每个查询时统计盘子数量,我们需要对每个查询区间进行遍历,这在最坏情况下的时间复杂度是O(n*m),其中n是字符串的长度,m是查询的数量。通过使用前缀和数组,我们可以预处理出一个数组,在O(1)的时间内回答任何区间内盘子的数量,从而使得每个查询的时间复杂度降低到O(1),整体上查询的总时间复杂度为O(m)。
🦆
在构建left和right数组时,如果在s字符串的起始或结束位置很长一段没有蜡烛,这种情况下如何保证算法的正确性?
在这种情况下,left数组在起始位置很长一段将记录为-1,表示没有找到任何蜡烛;right数组在结束位置很长一段也将记录为-1。在处理查询时,我们检查由right和left数组确定的蜡烛位置。如果这些位置为-1,说明在查询区间内没有蜡烛,或者蜡烛不满足在所查询的子区间内的条件。这种方式确保了即使在没有蜡烛的长段中,算法仍能正确地返回结果0,因为没有蜡烛意味着没有盘子可以被计数。
🦆
请问为什么要从右向左再次遍历字符串s来构建right数组?
从右向左遍历字符串s来构建right数组是为了记录每个位置右侧最近的蜡烛位置。这种从右向左的遍历方式允许我们在单次遍历中有效地更新右侧最近的蜡烛位置。如果我们只从左向右遍历,则无法在遍历过程中知道右侧的蜡烛位置,因此需要从右向左遍历以适应这一要求。
🦆
在处理查询时,如果查询区间内没有蜡烛怎么处理?
如果查询区间内没有蜡烛,则由right数组和left数组所确定的蜡烛位置将为-1。在算法实现中,我们首先检查由right[x]和left[y]确定的蜡烛位置是否有效(即不为-1)且right[x]小于left[y]。如果这些条件不满足,则查询区间内没有有效的蜡烛,因此返回的盘子数量应为0。这确保了在没有蜡烛的情况下算法返回正确的结果。

相关问题