leetcode系列贪心算法汇总

hot100系列

11 盛水最多的容器

题目：给一个一维数组，大概的意思就是下标代表水槽的宽度，数组的值代表这个位置水槽的高度，求盛水最多的容量。
解析：肯定得有个临时变量来存最大值，且不断进行比较来更新最大值，然后分别从两边开始使用双指针进行遍历，tmp := (right - left) * min(height[left], height[right])这个是计算公式，然后哪边的高度低就移动哪边的指针，最后返回最大值

55 跳跃游戏

题目：给一个一维数组，从起始位置开始，值代表从当前位置可以跳到的最远距离，问能不能走到末尾
解析：注意跳的范围能不能覆盖到末尾就行。大体的思路是定义一个变量来存可走到的范围，然后遍历这个范围，在范围的过程中不断更新范围的最大值cover = max(i + nums[i], cover)，如果cover大于了n，表示覆盖到了末尾

406 根据身高重建队列

题目：入参是people二维数组，people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人，返回排序后的结果
解析：这道题的解法很是巧妙，先要根据身高维度降序排，身高相等时根据k增序排，此时得到了一个中间态的结果，在此基础上进行遍历，根据每一个的k要在的相对位置进行不断的插入操作，巧妙的点就在于这种操作并不会影响之前已经排过的位置，因为身高是降序的，k是增序的

func reconstructQueue(people [][]int) [][]int {
	// 先将身高从大到小排列，确定最大个子的相对位置
	sort.Slice(people, func(i, j int) bool {
		if people[i][0] == people[j][0] {
			return people[i][1] < people[j][1] // 当身高相同是，将K按照从小到大排序
		}
		return people[i][0] > people[j][0] // 身高按照由大到小顺序来排
	})
	// 再按照K进行插入排序，优先插入K小的
	for i, p := range people {
		copy(people[p[1]+1:i+1], people[p[1]:i]) // 空出一个位置
		people[p[1]] = p
	}
	return people
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

581 最短无序连续子数组

题目：给一个一维数组，前后都是相对有序的，中间的经过排序后，整体也就有序了
解析：用题目中给的例子解释下：2 6 4 8 10 9 15
从左往右更新max的时候，会先被更新成6，遇到4的时候发现逆序了，把4更新成右边界，继续遇到8了更新成max，遇到10了更新成max，遇到9了，逆序，记录9为右边界，之后max更新成15。
从右往左更新min的时候，先是15，然后9，遇到10了逆序记录左边界，然后min更新成8，然后4，遇到6了逆序更新左边界，最后更新成2。
所以无序的区间就是从6到9的部分。

func findUnsortedSubarray(nums []int) int {
	n := len(nums)
	if n < 2 {
		return 0
	}
	leftMax := nums[0]    // 左边的最大值
	rightMin := nums[n-1] // 右边的最小值
	left := 0
	right := -1 // 因为最后结果要+1，比如默认有序的情况，所以这初始化为-1
	for i := 0; i < n; i++ {
		if leftMax > nums[i] {
			right = i
		} else {
			leftMax = nums[i]
		}

		if rightMin < nums[n-i-1] {
			left = n - i - 1
		} else {
			rightMin = nums[n-i-1]
		}
	}
	return right - left + 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

621 任务调度器

题目：两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态，计算完成任务的最短时间
解析：直接看这个的题解吧，解释不明白了：
添加链接描述

func leastInterval(tasks []byte, n int) int {
	var max int      // 最大值
	var maxCount int // 一共有多少个任务和出现最多的那个任务出现次数一样
	var s [26]int
	// 统计最多任务的个数
	for _, v := range tasks {
		s[v-'A']++
		if s[v-'A'] == max {
			maxCount++
		} else if s[v-'A'] > max {
			max = s[v-'A']
			maxCount = 1
		}
	}
    // maxTime为出现次数最多的那个任务出现的次数
	maxTime := (max-1)*(n+1) + maxCount
	if maxTime < len(tasks) {
		maxTime = len(tasks)
	}
	return maxTime
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21