def jump(self, nums: List[int]) -> int:
		l, r = 0, 0
		count = 0
		while r < len(nums) - 1:  # before r reaches the last index, continue
			farthest = 0
			for i in range(l, r + 1):
				farthest = max(farthest, i + nums[i])
			l = r + 1  # because it is guaranteed that I can rach the last index
			r = farthest
			count += 1
		return count

# 写法 1
	def maxSubArray(self, nums: List[int]) -> int:
		cur_max = nums[0]
		cur_sum = 0
		for num in nums:
			if cur_sum < 0:
				cur_sum = 0
				
			cur_sum += num
			cur_max = max(cur_max, cur_sum)

		return cur_max

# 写法 2
	def maxSubArray(self, nums: List[int]) -> int:
		cur_max_sum = nums[0]
		cur_sum = cur_max_sum
		for i in range(1, len(nums)):
			num = nums[i]
			if cur_sum > 0:
				cur_sum += num
			else:  # the previous sum doesn't help, and thus reset cur_sum to be current num. 0 doesn't help, and thus the condition is > 0
				cur_sum = num
			cur_max_sum = max(cur_max_sum, cur_sum)

		return cur_max_sum

# solution 1
	def canJump(self, nums: List[int]) -> bool:
		goal = len(nums) - 1
		for i in range(len(nums) - 1, -1, -1):
			if i + nums[i] >= goal:
				goal = i

		return goal == 0

# solution 2
def canJump(self, nums: List[int]) -> bool:
		l = 0
		r = 0 + nums[0]
		while True:
			cur_l = l
			cur_r = r
			for i in range(cur_l, cur_r + 1):
				r = max(r, i + nums[i])
				if r >= len(nums) - 1:
					return True
			if r == cur_r:
				return False
			l = cur_r + 1

	def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
		if sum(gas) < sum(
				cost):  # If this case, we know that we are not able to finish the route in any ways, because we know that the total gas is not enough
			return -1

		# If comes to here, we guarantee that we are able to finish the circular route
		left = 0
		res = 0
		for idx in range(len(gas)):
			left += gas[idx] - cost[idx]
			if left < 0:
				res = idx + 1
				left = 0
		# Because every time we pass every gas station and left >= 0, and sum(cost) <= sum(gas), so the pgas needed for the gas stations that we haven't gone through will be < than the left.
		return res

	def checkValidString(self, s: str) -> bool:
		# ( * ) * ( )
		minLeft = 0
		maxLeft = 0
		# space: O(1)
		# time: O(n)
		for char in s:
			if char == "(":
				minLeft += 1
				maxLeft += 1
			elif char == ")":
				minLeft -= 1
				maxLeft -= 1
			else:
				minLeft -= 1
				maxLeft += 1

			if maxLeft < 0:  # e.g., ))((
				return False
			if minLeft < 0:  # we need this if because of s = ( * ) ( case
				minLeft = 0
		return minLeft == 0

	def partitionLabels(self, s: str) -> List[int]:
		# get the last index of every element
		lastIndex = {}
		for idx in range(len(s)):
			char = s[idx]
			lastIndex[char] = idx

		res = []
		max_last_idx = 0
		size = 0
		for idx in range(len(s)):
			char = s[idx]

			max_last_idx = max(max_last_idx, lastIndex[char])
			size += 1
			if idx == max_last_idx:  # reach the last index of all elements that we have seen
				res.append(size)
				size = 0  # reset the size

		return res

	def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
		if len(hand) % groupSize != 0:
			return False

		m = {}
		for ele in hand:
			m[ele] = m.get(ele, 0) + 1

		minHeap = list(m.keys())
		heapq.heapify(minHeap)

		while minHeap:
			cur_min = minHeap[0]
			for i in range(cur_min, cur_min + groupSize):
				if i not in m:
					return False
				m[i] -= 1
				if m[i] == 0:
					if i != minHeap[0]:
						return False
					heapq.heappop(minHeap)
		return True

	def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
		hasX = False
		hasY = False
		hasZ = False
		for triplet in triplets:
			if triplet[0] > target[0] or triplet[1] > target[1] or triplet[2] > target[
				2]:  # Not consider such a triplet, since any of elements of this triplet is > than the corrsponding element in the target array, we shouldn't consider this triplet, otherwise, we cannot form target if we use this triplet, e.g., triplet: [2,8,3] target: [2,7,3] -> the final triplet will be [x,8,x]
				continue

			# Then, for all triplets come to here, the element will <= the element of the target, and if = for all three elements, we are sure that we can make it somehow
			if triplet[0] == target[0]:
				hasX = True
			if triplet[1] == target[1]:
				hasY = True
			if triplet[2] == target[2]:
				hasZ = True

		return hasX and hasY and hasZ