天池 在线编程 停车困境（双指针）

1. 题目

描述 停车场里停着许多汽车。 停车位是一条很长的直线，每米都有一个停车位。 当前很多汽车停放，您想通过建造屋顶来遮雨挡雨。 要求至少有k辆车的车顶被车顶遮盖，要覆盖k辆车的车顶的最小长度是多少？

该函数具有以下参数： cars：长度的整数数组，表示停放汽车的停车位 k：整数，表示必须被车顶遮盖的汽车数量 1 <= n <= 10^5 1 <= k <= n 0 <= cars[i] <= 10^14 所有车位上面的车都是唯一的

代码语言：javascript复制

示例:
输入:
cars: [2, 10, 8, 17]
k: 3
输出: 9
解释：您可以建立长度为9的屋顶，覆盖从第2个到第10个的所有停车位，
因此在第2、10、8个位置覆盖3辆车，没有较短的可以覆盖3辆车的车顶，
所以答案是 9

2. 解题

• 排序 双指针

代码语言：javascript复制

class Solution {
public:
    /**
     * @param cars:  integer array of length denoting the parking slots where cars are parked
     * @param k: integer denoting the number of cars that have to be covered by the roof
     * @return: ParkingDilemma
     */
    int ParkingDilemma(vector<int> &cars, int k) {
        // write your code here
        sort(cars.begin(), cars.end());
        int minlen = INT_MAX;
        int i = 0, j = 0, n = cars.size();
        int count = 0;
        while(j < n)
        {
            while(j < n && count < k)
            { // 个数不够 k 个
                j  ;
                count  ;
            }
            if(count == k)
            {
                minlen = min(minlen, cars[j-1]-cars[i] 1);
                count --;
                i  ;
            }
        }
        return minlen == INT_MAX ? -1 : minlen;
    }
};

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

https 网络安全 汽车

0 人点赞