Yuan's blog

刘沛源的博客

0%

std sort踩坑

发表于 更新于 Disqus：
本文字数： 82 阅读时长 ≈ 1 分钟

T135 会在下列输入时报错

1
[1,2,3,5,4,3,2,1,4,3,2,1,3,2,1,1,2,3,4,4,3,2,1]

可能跟sort内部实现有关，记得要使用 <= 而不要用 >

错误版本代码

sort 里面使用 <=

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
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> index(ratings.size());
        for (int i=0; i<index.size(); i++) {
            index[i] = i;
        }
        sort(index.begin(), index.end(), [&ratings](int ind1, int ind2) {
            return ratings[ind1] <= ratings[ind2];
        });

        vector<int> candy(ratings.size());
        for(auto ind: index) {
            int ct = 1;
            if(ind-1 >= 0 && ratings[ind] > ratings[ind-1]) {
                ct = max(candy[ind-1] + 1, ct);
            }
            if(ind+1 < ratings.size() && ratings[ind] > ratings[ind+1]) {
                ct = max(candy[ind+1] + 1, ct);
            }
            candy[ind] = ct;
        }

        return accumulate(candy.begin(), candy.end(), 0);
        
    }
};

正确版本代码

sort 里面使用 <

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
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> index(ratings.size());
        for (int i=0; i<index.size(); i++) {
            index[i] = i;
        }
        sort(index.begin(), index.end(), [&ratings](int ind1, int ind2) {
            return ratings[ind1] < ratings[ind2];
        });

        vector<int> candy(ratings.size());
        for(auto ind: index) {
            int ct = 1;
            if(ind-1 >= 0 && ratings[ind] > ratings[ind-1]) {
                ct = max(candy[ind-1] + 1, ct);
            }
            if(ind+1 < ratings.size() && ratings[ind] > ratings[ind+1]) {
                ct = max(candy[ind+1] + 1, ct);
            }
            candy[ind] = ct;
        }

        return accumulate(candy.begin(), candy.end(), 0);
        
    }
};