代码随想录1刷—贪心算法篇（一）_算法随想录网站

贪心理论基础

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

贪心没有套路，没有模板，刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。

455. 分发饼干

为了满足更多的小孩，就不要造成饼干尺寸的浪费。大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。

这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。可以尝试使用贪心策略，先将饼干数组和小孩数组排序。然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = s.size() - 1;       //饼干数组的下标
            //技巧 ，用index自减来控制饼干数组的遍历而不是for
        int result = 0;
        for(int i = g.size() - 1; i >= 0; i--){
            if(index >= 0 && s[index] >= g[i]){
                result++;
                index--;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

376. 摆动序列

贪心解法

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() <= 1)
            return nums.size();
        int curDiff = 0;    //当前一对的差值
        int preDiff = 0;    //前一对的差值
        int result = 1;     //峰值个数，默认序列最右有一个峰值
        for(int i = 0; i < nums.size() - 1; i++){
            curDiff = nums[i + 1] - nums[i];    //计算差值
            //出现峰值
            if((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)){
                result++;
                preDiff = curDiff;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

动态规划解法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IVM1ACqZ-1657264177136)(https://pic.leetcode-cn.com/1633692974-LMTDNI-%E8%87%AA%E5%AE%9A%E4%B9%89%20(5)].png)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rbXRYdKE-1657264177137)(https://cdn.jsdelivr.net/gh/mozro0327/mynotes/images/20220707140432.png)]

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int dp[nums.size()][2];
        dp[0][0] = dp[0][1] = 0;
        int i = 1;
        for (; i < nums.size(); i++) {
            //dp[i][0]降序结尾
            //dp[i][1]升序结尾
            if (nums[i] > nums[i-1]){
                dp[i][0] = dp[i-1][0];
                dp[i][1] = dp[i-1][0]+1;
            }else if (nums[i] < nums[i-1]){
                dp[i][0] = dp[i-1][1]+1;
                dp[i][1] = dp[i-1][1];
            }else{
                //相等
                dp[i][0] = dp[i-1][0];
                dp[i][1] = dp[i-1][1];
            }
        }
        return max(dp[nums.size() - 1][0],dp[nums.size() - 1][1]) + 1;
    }
};

//  if 升 {
//     dp[i][降] = dp[i-1][降]
//     dp[i][升] = dp[i-1][降]+1
//  }
//  if 降{
//      dp[i][降] = dp[i-1][升]+1
//      dp[i][升] = dp[i-1][升]
//  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

53. 最大子数组和

暴力解法（超时）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT_MIN;
        int count = 0;
        for(int i = 0; i < nums.size(); i++){
            count = 0;
            for(int j = i; j < nums.size(); j++){
                count += nums[j];
                result = count > result ? count : result;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

贪心解法

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。全局最优：选取最大“连续和”。

局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

从代码角度上来讲：遍历nums，从头开始用count累积，如果count一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积count了，因为已经变为负数的count，只会拖累总和。这相当于是暴力解法中的不断调整最大子序和区间的起始位置。

**那区间终止位置不用调整么？ 如何才能得到最大“连续和”呢？**区间的终止位置，其实就是如果count取到最大值了，及时记录下来了。代码如下：

if (count > result) result = count;	
//这样相当于是用result记录最大子序和区间和（变相的算是调整了终止位置）。
1
2

红色的起始位置就是贪心每次取count为正数的时候，开始一个区间的统计。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT_MIN;
        int count = 0;
        for(int i = 0; i < nums.size(); i++){
            count += nums[i];
            if(count > result){
                result = count;
            }
            if(count <= 0){
                count = 0;
            }
        }
        return result;
    }
};

//注意：是不能 让“连续和”为负数的时候 加上下一个元素，而不是 不让“连续和”加上一个负数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

动态规划解法

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        vector<int> dp(nums.size(), 0);  				//dp[i]表示包括i之前的最大连续子序列和
        dp[0] = nums[0];
        int result = dp[0];
        for(int i = 1; i < nums.size(); i++){
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);  //状态转移公式
            if(dp[i] > result)
                result = dp[i];
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

122. 买卖股票的最佳时机 II

贪心解法

如果想到其实最终利润是可以分解的，那么本题就很容易了！

假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。**此时就是把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！**那么根据prices可以得到每天的利润序列：(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。

第一天没有利润，至少要第二天才会有利润，所以利润的序列比股票序列少一天！从图中可以发现，其实我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。那么只收集正利润就是贪心所贪的地方！

局部最优：收集每天的正利润，全局最优：求得最大利润。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result = 0;
        for(int i = 1; i < prices.size(); i++){
            result += max(prices[i] - prices[i-1], 0);
        }
        return result;
    }   
};
1
2
3
4
5
6
7
8
9
10

动态规划解法

• 定义状态 dp[i][0] 表示第 i 天交易完后手里没有股票的最大利润；
• 定义状态 dp[i][1] 表示第 i 天交易完后手里持有股票的最大利润；
• 状态转移方程：
  • 考虑 dp[i][0] 的转移，无非是上一天没有股票这一天也没买或者是上一天持有股票而这一天卖了，求这两种情况下的最大利润即可：
    • dp[i][0] = max{dp[i−1][0], dp[i−1][1] + prices[i]}
  • 考虑 dp[i][1] 的转移，无非是上一天持有股票这一天没卖或者是上一天没有股票而这一天买了，求这两种情况下的最大利润即可：
    • dp[i][1] = max{dp[i−1][1], dp[i−1][0] - prices[i]}
• 明确初值：dp[0][0] = 0 和 dp[0][1] = -prices[0]
• 最终由于 dp[n-1][0] > dp[n-1][1] ，最大利润即为 dp[n-1][0] ，返回即可。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //dp[i][0]  表示第 i 天交易完后手里没有股票的最大利润
        //dp[i][1]  表示第 i 天交易完后手里持有股票的最大利润
        int n = prices.size();
        vector<vector<int>> dp(n,vector<int>(2,0));
        dp[0][0] = 0;
        dp[0][1] = - prices[0];
        for(int i = 1; i < n; i++){
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

55. 跳跃游戏

核心：跳跃覆盖范围究竟可不可以覆盖到终点

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。而cover每次只取 max(该元素数值补充后的范围, cover本身范围)。如果cover大于等于了终点下标，直接return true就可以了。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        if(nums.size() == 1) return true;
        for(int i = 0; i <= cover ;i++){
            cover = max(i + nums[i], cover);
            if(cover >= nums.size() - 1)
                return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

45. 跳跃游戏 II（晕乎乎）

贪心解法（一）

贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数。思路虽然是这样，但在写代码的时候还不能真的就能跳多远跳远，那样就不知道下一步最远能跳到哪里了。

所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数！这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

当移动下标达到了当前覆盖的最远距离下标时：

• 如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
• 如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() == 1) return 0;
        int curDistance = 0;	// 当前覆盖最远距离下标
        int ans = 0;			// 记录走的最大步数
        int nextDistance = 0;	// 下一步覆盖最远距离下标
        for(int i = 0;i < nums.size(); i++){
            nextDistance = max(i + nums[i], nextDistance);	// 更新下一步覆盖最远距离下标
            if(i == curDistance){							// 遇到当前覆盖最远距离下标
                if(curDistance != nums.size() - 1){			// 如果当前覆盖最远距离下标不是终点
                    ans++;
                    curDistance = nextDistance;				// 更新当前覆盖最远距离下标
                    if(nextDistance >= nums.size() - 1){	
                        break;					// 下一步的覆盖范围已经可以达到终点，结束循环
                    }
                }else if(curDistance == nums.size() - 1){
                    break;						// 如果当前覆盖最远距离下标是终点，结束循环
                }
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

贪心解法（二）

针对于方法一的特殊情况，可以统一处理，即：移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。想要达到这样的效果，只要让移动下标，最大只能移动到nums.size - 2的地方就可以了。因为当移动下标指向nums.size - 2时：

• 如果移动下标等于当前覆盖最大距离下标， 需要再走一步（即ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置），如图：

  

• 如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。如图：

class Solution {
public:
    int jump(vector<int>& nums) {
        int curDistance = 0;    // 当前覆盖的最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextDistance = 0;   // 下一步覆盖的最远距离下标
        for (int i = 0; i < nums.size() - 1; i++) { 
                                // 注意这里是小于nums.size() - 1，这是关键所在
            nextDistance = max(nums[i] + i, nextDistance); // 更新下一步覆盖的最远距离下标
            if (i == curDistance) {                 // 遇到当前覆盖的最远距离下标
                curDistance = nextDistance;         // 更新当前覆盖的最远距离下标
                ans++;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

理解本题的关键在于：以最小的步数增加最大的覆盖范围，直到覆盖范围覆盖了终点，这个范围内最小步数一定可以跳到，不用管具体是怎么跳的，不纠结于一步究竟跳一个单位还是两个单位。

1005. K 次取反后最大化的数组和

贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。

如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和达到最大。那么又是一个贪心：局部最优：只找数值最小的正整数进行反转，当前数值可以达到最大，全局最优：整个 数组和 达到最大。

本题的解题步骤为：

• 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
• 第二步：从前向后遍历，遇到负数将其变为正数，同时K–
• 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
• 第四步：求和

class Solution {
static bool cmp(int a,int b){
    return abs(a)>abs(b);   //abs为绝对值，a>b为降序
}
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end(),cmp);  //cmp为自己定义的排序规则
        for(int i = 0;i < nums.size() ;i++){
            if(nums[i]<0 && k>0){
                nums[i] = -nums[i];
                k--;
            }
        }
        if(k % 2 == 1){
            nums[nums.size() - 1] = - nums[nums.size() - 1];
        }
        int result = 0;
        for(int a:nums){
            result += a;
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

134. 加油站

暴力解法（超时）

// 遍历每一个加油站为起点的情况，模拟一圈。
// 如果跑了一圈，中途没有断油，而且最后油量大于等于0，说明这个起点是ok的。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        for(int i = 0;i < cost.size();i++){
            int rest = gas[i] - cost[i];    //剩余油量
            int index = (i + 1) % cost.size();  //计算开向的加油站号数（索引）
            while(rest > 0 && index != i){   //模拟以i为起点走一圈
                rest += gas[index] - cost[index];
                index = (index + 1) %cost.size();   //计算开向的加油站号数（索引）
            }
            if(rest >= 0 && index == i) 
            //开向的索引==i，此时如果油量大于0则返回该起始位置
                return i;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

贪心算法（一）

直接从全局进行贪心选择，情况如下：

• 情况一：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的。
• 情况二：rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
• 情况三：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能这个负数填平，能把这个负数填平的节点就是出发节点。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int min = INT_MAX;  //油量最小值
        for(int i = 0;i<gas.size();i++){
            int rest = gas[i] - cost[i];
            curSum += rest;
            if(curSum < min){
                min = curSum;
            }
        }
        if(curSum < 0) return -1;   //情况1
        if(min >= 0) return 0;      //情况2
        for(int i = gas.size()-1; i>=0; i--){   //情况3
            int rest = gas[i] - cost[i];
            min += rest;
            if(min >= 0){
                return i;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

贪心算法（二）

换一个思路，如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。每个加油站的剩余量rest[i]为gas[i] - cost[i]。

i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。

局部最优：当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1，因为从j开始一定不行。全局最优：找到可以跑一圈的起始位置。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for(int i= 0;i<gas.size();i++){
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if(curSum < 0){
                start = i + 1;
                curSum = 0;
            }
        }
        if(totalSum < 0)    return -1;
        return start;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

135. 分发糖果

本题采用了两次贪心的策略：

• 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
• 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

1、先确定右边评分大于左边的情况（也就是从前向后遍历）

此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果。如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个，所以贪心：candyVec[i] = candyVec[i - 1] + 1

2、再确定左孩子大于右孩子的情况（从后向前遍历）

如果 ratings[i] > ratings[i + 1]，此时candyVec[i]（第i个小孩的糖果数量）就有两个选择了，一个是candyVec[i + 1] + 1（从右边这个加1得到的糖果数量），一个是candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）。此时取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多。

局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量即大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyvec(ratings.size(),1);
        for(int i = 1;i<ratings.size();i++){    //右边
            if(ratings[i]>ratings[i-1]){
                candyvec[i] = candyvec[i-1]+1;
            }
        }
        for(int i = ratings.size()-2;i>=0;i--){ //左边
            if(ratings[i]>ratings[i+1]){
                candyvec[i] = max(candyvec[i],candyvec[i+1]+1); //保证其大于左边的也大于右边的
            }
        }
        int result = 0;
        for(int i= 0;i<candyvec.size();i++){
            result+=candyvec[i];
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

860. 柠檬水找零

• 情况一：账单是5，直接收下。
• 情况二：账单是10，消耗一个5，增加一个10
• 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

情况一，情况二，都是固定策略，唯一不确定的其实在情况三。账单是20的情况，为什么要优先消耗一个10和一个5呢？因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！

所以局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0,ten = 0,twenty = 0;
        for(int i = 0;i < bills.size();i++){
            if(bills[i] == 5)   five++;
            if(bills[i] == 10){
                if(five <= 0) return false;
                ten++;five--;
            }
            if(bills[i] == 20){
                if(five>0 && ten>0){
                    ten--;five--;twenty++;
                }else if(five >= 3){
                    five -= 3;
                    twenty++;
                }else return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

406. 根据身高重建队列

题目有两个维度，一个是身高h，一个是前面有多少个身高大于等于当前h的人。

首先，两个维度情况下，需要一个个维度来进行，不能并行（会顾此失彼），那么在身高h和比较k中，如果先选择k，则得到k的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来。因此选择h先进行排序，由于要求中k为前面有多少个身高大于等于当前h的人，因此h进行降序，得到身高从高到低的序列（其中如果身高相同，则将k小的放在前面）。此时得到：前面的节点一定都比本节点高的序列。

然后进行k维度的处理，按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。所以在按照身高从大到小排序后，局部最优：优先按身高高的k来插入。插入操作过后的people满足队列属性，全局最优：最后都做完插入操作，整个队列满足题目队列属性。

排序完的people： [[7,0], [7,1], [6,1], [5,0], [5,2]，[4,4]]

插入的过程：

• 插入[7,0]：[[7,0]]
• 插入[7,1]：[[7,0],[7,1]]
• 插入[6,1]：[[7,0],[6,1],[7,1]]
• 插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
• 插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
• 插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

数组版本

class Solution {
    static bool cmp(const vector<int>& a,const vector<int>& b){
        if(a[0] == b[0]){       //第一个值身高相等
            return a[1] < b[1];     //返回第二个值较小的放在前面
        }
        return a[0] > b[0];     //身高较大的放在前面 
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),cmp);
        vector<vector<int>> que;
        for(int i = 0;i < people.size();i++){
            int position = people[i][1];
            que.insert(que.begin() + position,people[i]);
        }
        return que;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 时间复杂度：$O(nlogn+n^2)$
• 空间复杂度：$O(n)$

使用vector是非常费时的，C++中vector（可以理解是一个动态数组，底层是普通数组实现的）**如果插入元素大于预先普通数组大小，vector底部会有一个扩容的操作，即就是重新申请一个二倍于原数组大小的数组，然后把数据都拷贝过去，并释放原数组内存。**所以使用vector（动态数组）来insert，是费时的。

虽然表面上复杂度是$O(n^2)$，但是其底层都不知道额外做了多少次全量拷贝了，所以算上vector的底层拷贝，整体时间复杂度可以认为是$O(n^2+t\times n)$级别的，t是底层拷贝的次数。

那么是不是可以直接定义好一个固定大小的vector，这样就可以控制vector，不让它底层动态扩容？

这种方法需要自己模拟插入的操作，不仅没有直接调用insert接口那么方便，需要手动模拟插入操作，而且效率也不高！可能是就算避免的vector的底层扩容，但这个固定大小的数组，每次向后移动元素赋值的次数说不定会比动态中移动赋值的次数要多很多。

因为vector一开始数组是很小的，插入操作，向后移动元素次数比较少，即使有偶尔的扩容操作。而固定大小的vector每次都是按照最大数组规模向后移动元素的。所以对于两种使用数组的方法，也不好确定谁优谁劣，要看数据元素的多少。

class Solution {
    static bool cmp(const vector<int>& a,const vector<int>& b){
        if(a[0] == b[0]){       //第一个值身高相等
            return a[1] < b[1];     //返回第二个值较小的放在前面
        }
        return a[0] > b[0];     //身高较大的放在前面 
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),cmp);
        vector<vector<int>> que(people.size(), vector<int>(2, -1));
                //初始化后得到que: {{-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}……（people.size()）
        for(int i = 0;i < people.size();i++){
            int position = people[i][1];
            if (position == que.size() - 1) que[position] = people[i];
            else { // 将插入位置后面的元素整体向后移
                for (int j = que.size() - 2; j >= position; j--) que[j + 1] = que[j];
                que[position] = people[i];
            }
        }
        return que;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

链表版本

class Solution {
    static bool cmp(const vector<int>& a,const vector<int>& b){
        if(a[0] == b[0]){       //第一个值身高相等
            return a[1] < b[1];     //返回第二个值较小的放在前面
        }
        return a[0] > b[0];     //身高较大的放在前面 
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),cmp);
        list<vector<int>> que;
        for(int i = 0;i < people.size();i++){
            int position = people[i][1];
            std::list<vector<int>>::iterator it = que.begin();
            while(position--){
                it++;
            }
            que.insert(it,people[i]);
        }
        return vector<vector<int>>(que.begin(),que.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22