灵神常见算法

283. 移动零

• 题目需要不复制数组，可使用双指针。
• i指针往后遍历
• j指针指向已经排好的数组的尾部。

i, j
0	1	0	3	12

一开始i、j指针都指向0位置。

j	i
0	1	0	3	12

j	i
1	0	0	3	12

i指针找到第一个不为0的数，与j指针指向的数交换。

j			i
1	0	0	3	12

j			i
1	3	0	0	12

i指针找到第二个不为0的数，交换。

j				i
1	3	0	0	12

j				i
1	3	12	0	0

结束。

func moveZeroes(nums []int) {
	j := 0 // 已经排好的数组，末尾位置
	for i, v := range nums {
		if v != 0 {
			// 交换
			t := nums[i]
			nums[i] = nums[j]
			nums[j] = t

			j++
		}
	}
}

11. 盛最多水的容器

• 容纳的水体积：左右最低的

func maxArea(height []int) int {
	n := len(height)
	left, right := 0, n-1
	ans := 0

	for left < right {
		// 求面积
		area := min(height[left], height[right]) * (right - left)
		ans = max(area, ans)

		// 如果移动高的一边，高度受限于短板，高度不变，宽度减少，因此移动低的一边。
		if height[left] < height[right] {
			left++
		} else {
			right--
		}
	}

	return ans
}