贪心

763. Partition Labels

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        dic = dict()                  # 记录char最后出现的位置
        for idx, ch in enumerate(s):
            dic[ch] = idx
        partition = []
        start = end = 0
        for idx, ch in enumerate(s):
            end = max(end, dic[ch])
            if idx == end:
                res.append(end - start + 1)
                start = end = idx + 1
        return partition

• 时间复杂度：
• 空间复杂度：

55. Jump Game

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        end = len(nums) - 1        # 终点
        rightmost = 0              # 最远可以到达的位置
        for index, num in enumerate(nums):
            if index > rightmost:  # 当前位置已经不可达
                break
            rightmost = max(rightmost, index + num)
            if rightmost >= end:
                return True
        return False

• 时间复杂度：
• 空间复杂度：

45. Jump Game II

从的位置逆向寻找上一步的位置，贪心地考虑，若上一步位置越靠前，则使用的步数越少。故正向遍历到当前位置。

class Solution:
    def jump(self, nums: List[int]) -> int:
        position = len(nums) - 1
        steps = 0
        while position > 0:
            for i in range(position):
                if i + nums[i] >= position:
                    position = i
                    steps += 1
                    break
        return steps

• 时间复杂度：，考虑最坏情况，用例为
• 空间复杂度：

正向考虑，注意不要访问最后一个元素。

class Solution:
    def jump(self, nums: List[int]) -> int:
        rightmost = 0
        end_step = 0
        num_step = 0

        for index, num in enumerate(nums[:-1]):
            rightmost = max(rightmost, index + num)
            if index == end_step:
                num_step += 1
                end_step = rightmost
                if end_step >= len(nums) - 1:
                    break

        return num_step

• 时间复杂度：
• 空间复杂度：

135. Candy

每个孩子至少分到个糖果，且：
相邻两个孩子，评分更高的会获得更多的糖果 满足**左右规则**

• 左规则：若，则会得到更多糖果；

• 右规则：若，则会得到更多糖果。

  class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n
  
        for i in range(1, n):                    # 满足'左'规则
            if ratings[i-1] < ratings[i]:
                candies[i] = candies[i-1] + 1
  
        for i in range(n - 2, -1, -1):           # 满足'右'规则
            if ratings[i] > ratings[i+1]:
                candies[i] = max(candies[i], candies[i+1] + 1)
  
        return sum(candies)
  

• 时间复杂度：

• 空间复杂度：

31. Next Permutation

贪心思路：

1. 拟寻找一个数对pair ，满足并且要尽可能靠右，要尽可能小（最接近a）；
2. 交换和，并将后方的数字翻转。

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:    # 逆序寻找'较小数'
            i -= 1

        if i >= 0:                                  # 排列不是全逆序
            j = n - 1
            while j > i and nums[i] >= nums[j]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

        left, right = i + 1, n - 1                  # 翻转后方元素（全逆序）
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

• 时间复杂度：
• 空间复杂度：

低频：每日一题

942. DI String Match

1. 当s[i] == 'I'时，使用可选择区间的来构造
2. 当s[i] == 'D'时，使用可选择区间的来构造

重复以上过程，不断构造出子问题，贪心地求解出全局最优解。其中，可选择区间由双指针来维护。

class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        res = []
        left, right = 0, len(s)

        for ch in s:
            if ch == 'I':
                res.append(left)
                left += 1
            elif ch == 'D':
                res.append(right)
                right -= 1

        return res + [left]

• 时间复杂度：
• 空间复杂度：，不计算答案数组