1
class Solution:
2
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
3
        n = len(gas)
4
        total, min_sum, start = 0, 0, 0
5

6
        for i in range(n):
7
            total += gas[i] - cost[i]
8
            if total < min_sum:
9
                # 当前总油量比历史最小值还小，更新起点为下一站
10
                min_sum = total
11
                start = i + 1
12

13
        if total < 0:
14
            return -1
15
        return 0 if start == n else start

1
class Solution:
2
    def candy(self, ratings: List[int]) -> int:
3
        n = len(ratings)
4
        if n == 0:
5
            return 0
6

7
        candies = [1] * n  # 每人至少一个
8

9
        # 从左到右，确保右边高分的孩子糖果更多
10
        for i in range(1, n):
11
            if ratings[i] > ratings[i - 1]:
12
                candies[i] = candies[i - 1] + 1
13

14
        # 从右到左，再次调整左边高分但糖果少的情况
15
        for i in range(n - 2, -1, -1):
16
            if ratings[i] > ratings[i + 1]:
17
                candies[i] = max(candies[i], candies[i + 1] + 1)
18

19
        return sum(candies)

1
class Solution:
2
    def lemonadeChange(self, bills: List[int]) -> bool:
3
        five, ten = 0, 0  # 初始化零钱数量
4

5
        for bill in bills:
6
            if bill == 5:
7
                five += 1
8
            elif bill == 10:
9
                if five <= 0:
10
                    return False
11
                five -= 1
12
                ten += 1
13
            else:  # bill == 20
14
                # 优先使用一个 10 和一个 5 找零
15
                if ten > 0 and five > 0:
16
                    ten -= 1
17
                    five -= 1
18
                elif five >= 3:
19
                    five -= 3
20
                else:
21
                    return False
22

23
        return True

1
class Solution:
2
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
3
        # 按身高降序，k值升序排序
4
        people.sort(key=lambda x: (-x[0], x[1]))
5

6
        self.insertSort(people)
7
        return people
8

9
    def insertSort(self, people):
10
        n = len(people)
11
        sorted_index = 0
12

13
        while sorted_index < n:
14
            # 将当前元素插入到前面正确的位置，使得前面有 k 个高于等于它的人
15
            for i in range(sorted_index, 0, -1):
16
                k = people[i][1]
17
                if k < i:
18
                    # 向前交换
19
                    people[i], people[i - 1] = people[i - 1], people[i]
20
                else:
21
                    break
22
            sorted_index += 1