Leetcode——881. 救生艇

首先从暴力解法入手，排序并遍历数组，接着根据题意，找是否有能同船者，且同船者对应数字应足够大。然后可以用一个数组标记是否使用过，暴力搜索即可。

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        int n = people.size();
        sort(people.begin(), people.end());
        vector<int> used(n, 0);
        int ans = 0;
        for(int i = 0; i < n; ++i){
            if(used[i] == 0){
                int otherIndex = findPeople(people, limit - people[i], used);
                if(otherIndex != -1){
                    used[otherIndex] = 1;
                }
                ans++;
                used[i] = 1;
            }
        }
        return ans;
    }

    int findPeople(vector<int>& peolpe, int target, vector<int>& used){
        int ans = -1;
        int index = -1;
        for(int i = 0; i < peolpe.size(); ++i){
            if(used[i] == 0){
                if(peolpe[i] <= target){
                    ans = max(ans, peolpe[i]);
                    index = i;
                }
            }
        }
        return index;
    }
};

不过很显然会超时，因为其每次都遍历数组。

考虑到数组已经排序，这样我们只需要从当前位置向后找即可。

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        int n = people.size();
        sort(people.begin(), people.end());
        vector<int> used(n, 0);
        int ans = 0;
        for(int i = 0; i < n; ++i){
            if(used[i] == 0){
                int otherIndex = findPeople(people, limit - people[i], used, i);
                if(otherIndex != -1){
                    used[otherIndex] = 1;
                }
                ans++;
                used[i] = 1;
            }
        }
        return ans;
    }

    int findPeople(vector<int>& peolpe, int target, vector<int>& used, int start){
        int ans = -1;
        int index = -1;
        for(int i = start + 1; i < peolpe.size(); ++i){
            if(used[i] == 0){
                if(peolpe[i] <= target){
                    ans = max(ans, peolpe[i]);
                    index = i;
                }
            }
        }
        return index;
    }
};

不过还是超时，那么根据这次的思路，发现较大者其实都是在排序后靠后的位置。

那么是否可以考虑双指针，一个记录最左（最小），一个记录最右（最大），当两者可以同船，左加右减；当两者不能同传，很显然最大的记录太大，让其自己做一条船即可，所以只需最右减，左不动。

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int l = 0, r = people.size() - 1;
        int ans = 0;
        while(l <= r){
            if(l == r){
                ans++;
                break;
            }
            if(people[l] + people[r] <= limit){
                l++;
            }
            ans++;
            r--;
        }
        return ans;
    }
};