leetcode881 救生艇

题目

救生艇

暴力解法：模拟(超时)

题目的意思其实就是给定一个数组，然后把这些数放到限定大小的位置，每个位置最多放两个数，且大小是最多是两个数的和。

根据题意就想到一种模拟的方法。因为题目说一定是可以完全放置的，所以不可能存在某一个数的大小超过limit，故最多的情况是每个数放一个位置，那么最多需要n个位置。

用一个长度为n的数组模拟这些位置。对原始数组从大到小排序，对每一个数都左到右遍历一下可以放到哪个位置。

时间复杂度：排序O(n * log(n)) + 两边循环O(n * n) = O(n * n)

代码

class Solution {
public:
    int numRescueBoats(vector<int>& nums, int limit) {
        sort(nums.begin(), nums.end(), greater<int>());

        vector<int> vec(nums.size(), 0);
        vector<int> cnt(nums.size(), 0);
        int k = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j <= k + 1; j++) {
                if (cnt[j] < 2 && vec[j] + nums[i] <= limit) {
                    vec[j] += nums[i];
                    cnt[j]++;
                    if (j == k + 1) {
                        k++;
                    }
                    break;
                }
            }
        }
        for (int i = 0; i < nums.size(); i++) {
            if (vec[i] == 0) {
                return i;
            }
        }

        return nums.size();
    }
};

排序 + 双指针

想到这个解法的关键点就在于每个位置最多放两个数，如果在某个位置我们放了一个最大的数，那么是不是只要判断一下最小的数能不能放在这里，就能确定这个位置仅由这个最大的数独占，还是和这个最小的数一起占有？我们可以简单证明一下。

对于一个排好序的数组num = [a1, a2, a3, an]，an最大，a1最小。如果a1 + an > limit，由于a2 >= a1，所以a2 + an > limit，说明如果an不和a1配对占有一个位置，必定就是an独占一个位置。

代码

class Solution {
public:
    int numRescueBoats(vector<int>& nums, int limit) {
        sort(nums.begin(), nums.end());
        
        int i = 0, j = nums.size() - 1;
        int res = 0;

        while (i <= j) {
            //最小的数和最大的数共同占有一个位置，指向小的位置的指针向后挪一位
            if (nums[i] + nums[j] <= limit) {
                i++;
            }
            //无论是否跟小的数一起占有，大的数总会占有一个位置。
            j--;
            res++;
        }
        return res;
    }
};