[数据结构与算法]leetcode 2055.蜡烛之间的盘子C++

链接：

leetcode2055

描述：

示例：

代码：

class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        int n = s.size();
        vector<int> preSum(n);
        for (int i = 0, sum = 0; i < n; i++) {
            if (s[i] == '*') {
                sum++;
            }
            preSum[i] = sum;
        }
        vector<int> left(n);
        for (int i = 0, l = -1; i < n; i++) {
            if (s[i] == '|') {
                l = i;
            }
            left[i] = l;
        }
        vector<int> right(n);
        for (int i = n - 1, r = -1; i >= 0; i--) {
            if (s[i] == '|') {
                r = i;
            }
            right[i] = r;
        }
        vector<int> ret;
        for (auto& query : queries) {
            int x = right[query[0]], y = left[query[1]];
            ret.push_back(x == -1 || y == -1 || x >= y ? 0 : preSum[y] - preSum[x]);
        }
        return ret;
    }
};

题目解析：

string表示按照这个符号顺序进行摆放盘子和蜡烛
queries表示的数组是，
其中的每一个小数组之间的范围

让我们求的是：
这个小数组[x,y]范围内，距离x最近的蜡烛和y最近的蜡烛
他们之间的盘子个数

代码分析：

先用数组表示string中每个位置之前有多少个盘子

left表示距离这个数组中元素左边的第一个蜡烛的位置
right表示距离这个数组中元素右边的第一个蜡烛的位置

当x , y == -1时间，表示这个位置的旁边没有蜡烛，直接返回零

当right的值比left大时，直接就是0

画图分析：