Leetcode模块训练1

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，
返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成
如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果
不需要考虑数组中超出新长度后面的元素

func removeDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	tempValue := nums[0]
	vCount := 1
	for _, v := range nums {
		if tempValue != v {
			nums[vCount] = v
			tempValue = v
			vCount++
		}
	}
	return vCount
}

//双指针
func removeDuplicates2(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	slow := 1
	for fast := 1; fast < len(nums); fast++ {
		if nums[fast] != nums[fast-1] {
			nums[slow] = nums[fast]
			slow++
		}
	}
	return slow
}

func main() {
	num := []int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}
	num2 := []int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}
	fmt.Println(removeDuplicates(num))
	fmt.Println(removeDuplicates2(num2))
}

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作

示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:
输入: nums = [0]
输出: [0]

//双指针，自己的写法
//时间复杂度：O(n)
//空间复杂度：O(1)
func moveZeroes1(nums []int) {
	length := len(nums)
	if length == 0 || length == 1 {
		return
	}
	prev, cur := 0, 1
	for cur < length && prev != cur {
		for nums[prev] != 0 && prev < cur {
			prev++
		}
		if nums[prev] == 0 && nums[cur] == 0 {
			cur++
		}
		if cur < length && nums[prev] == 0 && nums[cur] != 0 {
			tempData := nums[prev]
			nums[prev] = nums[cur]
			nums[cur] = tempData
			prev++
			cur++
		} else {
			cur++
		}
	}
}

//双指针，官方写法
//时间复杂度：O(n)
//空间复杂度：O(1)
func moveZeroes2(nums []int) {
	left, right, n := 0, 0, len(nums)
	for right < n {
		if nums[right] != 0 {
			nums[left], nums[right] = nums[right], nums[left]
			left++
		}
		right++
	}
}

func main() {
	nums := []int{0, 1, 0, 3, 12}
	moveZeroes1(nums)
	fmt.Println(nums)
}

给你两个按 非递减顺序 排列的整数数组nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，
其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

// 时间复杂度：O((m+n)log(m+n))。
// 空间复杂度：O(log(m+n))。
func merge1(nums1 []int, m int, nums2 []int, _ int) {
	copy(nums1[m:], nums2)
	sort.Ints(nums1)
}

// 自己写的 双指针
// 时间复杂度：O(m+n)
// 空间复杂度：O(m+n)
func merge2(nums1 []int, m int, nums2 []int, n int) {
	num0 := make([]int, m, m)
	for i := 0; i < m; i++ {
		num0[i] = nums1[i]
	}
	i, j, k := 0, 0, 0
	for i < m && j < n {
		if num0[i] < nums2[j] {
			nums1[k] = num0[i]
			i++
		} else {
			nums1[k] = nums2[j]
			j++
		}
		k++
	}
	if i == m {
		for p := k; p < m+n; p++ {
			nums1[p] = nums2[j]
			j++
		}
	} else if j == n {
		for p := k; p < m+n; p++ {
			nums1[p] = num0[i]
			i++
		}
	}
}

// 官方 双指针
// 时间复杂度：O(m+n)
// 空间复杂度：O(m+n)
func merge3(nums1 []int, m int, nums2 []int, n int) {
	sorted := make([]int, 0, m+n)
	p1, p2 := 0, 0
	for {
		if p1 == m {
			sorted = append(sorted, nums2[p2:]...)
			break
		}
		if p2 == n {
			sorted = append(sorted, nums1[p1:]...)
			break
		}
		if nums1[p1] < nums2[p2] {
			sorted = append(sorted, nums1[p1])
			p1++
		} else {
			sorted = append(sorted, nums2[p2])
			p2++
		}
	}
	copy(nums1, sorted)
}

// 官方 逆向双指针
// 时间复杂度：O(m+n)
// 空间复杂度：O(m+n)
func merge4(nums1 []int, m int, nums2 []int, n int) {
	for p1, p2, tail := m-1, n-1, m+n-1; p1 >= 0 || p2 >= 0; tail-- {
		var cur int
		if p1 == -1 {
			cur = nums2[p2]
			p2--
		} else if p2 == -1 {
			cur = nums1[p1]
			p1--
		} else if nums1[p1] > nums2[p2] {
			cur = nums1[p1]
			p1--
		} else {
			cur = nums2[p2]
			p2--
		}
		nums1[tail] = cur
	}
}

func main() {
	num1 := []int{1, 2, 3, 0, 0, 0}
	num2 := []int{2, 5, 6}
	m, n := 3, 3
	merge2(num1, m, num2, n)
}

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

示例1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：
输入：digits = [0]
输出：[1]

func plusOne(digits []int) []int {
	for i := len(digits) - 1; i >= 0; i-- {
		digits[i] += 1
		digits[i] %= 10
		if digits[i] != 0 {
			return digits
		}
	}
	return append([]int{1}, digits...)
}

func main() {
	nums := []int{4, 3, 2, 9}
	fmt.Println(plusOne(nums))
}

给一个单链表的头节点 head ，请你反转链表，并返回反转后的链表

例如：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

输入：head = []
输出：[]

type ListNode struct {
	Val  int
	Next *ListNode
}

//迭代法
//时间复杂度：O(n)
//空间复杂度：O(1)
func reverseList1(head *ListNode) *ListNode {
	var nPrev *ListNode
	nNow := head
	for nNow != nil {
		tempNode := nNow.Next
		nNow.Next = nPrev
		nPrev = nNow
		nNow = tempNode
	}
	return nPrev
}

//递归法
//时间复杂度：O(n)
//空间复杂度：O(n)
//递归过程
/*
  reverseList: head=1
    reverseList: head=2
	    reverseList: head=3
		    reverseList:head=4
			    reverseList:head=5
					终止返回
				cur = 5
				4.next.next->4，即5->4
			cur=5
			3.next.next->3，即4->3
		cur = 5
		2.next.next->2，即3->2
	cur = 5
	1.next.next->1，即2->1

	最后返回cur
*/
func reverseList2(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := reverseList2(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
}

func main() {
	node1 := new(ListNode)
	node2 := new(ListNode)
	node3 := new(ListNode)
	node4 := new(ListNode)
	node5 := new(ListNode)
	node1.Val = 1
	node1.Next = node2
	node2.Val = 2
	node2.Next = node3
	node3.Val = 3
	node3.Next = node4
	node4.Val = 4
	node4.Next = node5
	node5.Val = 5
	//a := reverseList1(node1)
	//for a != nil {
	//	fmt.Println(a.Val)
	//	a = a.Next
	//}

	b := reverseList1(node1)
	for b != nil {
		fmt.Println(b.Val)
		b = b.Next
	}
}

给你链表的头节点 head ，每k个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

例如：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

例如：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

type ListNode struct {
	Val  int
	Next *ListNode
}

func ReverseNode(head, tail *ListNode) (*ListNode, *ListNode) {
	prev := tail.Next
	p := head
	for prev != tail {
		nex := p.Next
		p.Next = prev
		prev = p
		p = nex
	}
	return tail, head
}

func reverseKGroup(head *ListNode, k int) *ListNode {
	hair := &ListNode{Next: head}
	pre := hair
	for head != nil {
		tail := pre
		for i := 0; i < k; i++ {
			tail = tail.Next
			if tail == nil {
				return hair.Next
			}
		}
		nex := tail.Next
		head, tail = ReverseNode(head, tail)
		pre.Next = head
		tail.Next = nex
		pre = tail
		head = tail.Next
	}

	return hair.Next
}

func main() {
	node1 := new(ListNode)
	node2 := new(ListNode)
	node3 := new(ListNode)
	node4 := new(ListNode)
	node5 := new(ListNode)
	node1.Val = 1
	node1.Next = node2
	node2.Val = 2
	node2.Next = node3
	node3.Val = 3
	node3.Next = node4
	node4.Val = 4
	node4.Next = node5
	node5.Val = 5
	node := reverseKGroup(node1, 2)
	for node != nil {
		fmt.Println(node.Val)
		node = node.Next
	}
}

给一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。

示例：
输入：head = [3,2,0,-4]，pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点

type ListNode struct {
	Val  int
	Next *ListNode
}

//方法一：哈希表法
//每次到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中
//时间复杂度：O(n)
//空间复杂度：O(n)
func hasCycle1(head *ListNode) bool {
	tempMap :=  map[*ListNode]struct{}{}
	for head != nil {
		if _, ok := tempMap[head]; ok {
			return true
		}
		tempMap[head] = struct{}{}
		head = head.Next
	}
	return false
}

//方法二：快慢指针法
//一个慢指针每次移动一步，一个快指针一次移动两步，当快指针追上慢指针后说明存在环
//时间复杂度：O(n)
//空间复杂度：O(1)
func hasCycle2(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return false
	}
	slow, fast := head, head.Next
	for slow != fast {
		if fast == nil || fast.Next == nil {
			return false
		}
		slow = slow.Next
		fast = fast.Next.Next
	}
	return true
}

func main() {
	node1 := new(ListNode)
	node2 := new(ListNode)
	node3 := new(ListNode)
	node4 := new(ListNode)
	node1.Val = 3
	node1.Next = node2
	node2.Val = 2
	node2.Next = node3
	node3.Val = 0
	node3.Next = node4
	node4.Val = -4
	node4.Next = node2

	cycle1 := hasCycle1(node1)
	fmt.Println(cycle1)

	cycle2 := hasCycle2(node1)
	fmt.Println(cycle2)
}

给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。
如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。

示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

type ListNode struct {
	Val  int
	Next *ListNode
}

//方法一：哈希表法
//每次到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中
//时间复杂度：O(n)
//空间复杂度：O(n)
func detectCycle1(head *ListNode) *ListNode {
	tempHead := head
	tempMap := make(map[*ListNode]struct{})
	for tempHead != nil {
		if _, ok := tempMap[tempHead]; ok {
			return tempHead
		}
		tempMap[tempHead] = struct{}{}
		tempHead = tempHead.Next
	}
	return nil
}

func main() {
	node1 := new(ListNode)
	node2 := new(ListNode)
	node3 := new(ListNode)
	node4 := new(ListNode)
	node1.Val = 3
	node1.Next = node2
	node2.Val = 2
	node2.Next = node3
	node3.Val = 0
	node3.Next = node4
	node4.Val = -4
	node4.Next = node2

	result := detectCycle1(node1)
	fmt.Println(result.Val)
}

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例1:
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

type ListNode struct {
	Val  int
	Next *ListNode
}

//递归法
func mergeTwoLists1(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}

	if l2 == nil {
		return l1
	}

	var result *ListNode
	if l1.Val <= l2.Val {
		result = l1
		result.Next = mergeTwoLists1(l1.Next, l2)
	} else {
		result = l2
		result.Next = mergeTwoLists1(l1, l2.Next)
	}

	return result
}

//迭代法
//会比用递归占用更少的空间
func mergeTwoLists2(l1 *ListNode, l2 *ListNode) *ListNode {
	nodeTemp := &ListNode{}
	current := nodeTemp

	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			current.Next = l1
			l1 = l1.Next
		} else {
			current.Next = l2
			l2 = l2.Next
		}
		current = current.Next
	}

	if l1 != nil {
		current.Next = l1
	} else {
		current.Next = l2
	}
	return nodeTemp.Next
}

func main() {
	var h1 = new(ListNode)
	h1.Val = 1
	var h2 = new(ListNode)
	h2.Val = 2
	var h3 = new(ListNode)
	h3.Val = 4
	h1.Next = h2
	h2.Next = h3
	h3.Next = nil

	var h11 = new(ListNode)
	h11.Val = 1
	var h22 = new(ListNode)
	h22.Val = 3
	var h33 = new(ListNode)
	h33.Val = 4
	h11.Next = h22
	h22.Next = h33
	h33.Next = nil

	//result1 := mergeTwoLists1(h1, h11)
	//fmt.Println(result1)

	result2 := mergeTwoLists2(h1, h11)
	fmt.Println(result2)
}

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：
输入：s = "()[]{}"
输出：true

示例 2：
输入：s = "{[]}"
输出：true

示例 3：
输入：s = "([)]"
输出：false

//时间复杂度：O(N)
//空间复杂度：O(N+E)，E表示括号的个数
//栈的思想
func isValid(s string) bool {
	if len(s)%2 == 1 {
		return false
	}
	mapTemp := map[byte]byte{
		')': '(',
		']': '[',
		'}': '{',
	}
	var stack []byte
	for i := 0; i < len(s); i++ {
		if v, ok := mapTemp[s[i]]; ok {
			if len(stack) == 0 || stack[len(stack)-1] != v {
				return false
			}
			stack = stack[:len(stack)-1]
		} else {
			stack = append(stack, s[i])
		}
	}
	return len(stack) == 0
}

func main() {
	s := "()[]{}"
	b := isValid(s)
	fmt.Println(b)
}

别名：后缀表达式求值
根据 逆波兰表示法，求表达式的值。
有效的算符包括+、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

/*
时间复杂度：O(n)
空间复杂度：O(n)
*/
func evalRPN(tokens []string) int {
	var stack []int
	for _, token := range tokens {
		val, err := strconv.Atoi(token)
		if err == nil {
			stack = append(stack, val)
		} else {
			num1, num2 := stack[len(stack)-2], stack[len(stack)-1]
			stack = stack[0 : len(stack)-2]
			switch token {
			case "+":
				stack = append(stack, num1+num2)
			case "-":
				stack = append(stack, num1-num2)
			case "*":
				stack = append(stack, num1*num2)
			default:
				stack = append(stack, num1/num2)
			}
		}
	}
	return stack[0]
}

func main() {
	tokens := []string{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"}
	fmt.Println(evalRPN(tokens))
}

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：
输入：s = "1 + 1"
输出：2

示例 2：
输入：s = " 2-1 + 2 "
输出：3

示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

/*
时间复杂度：O(n)
空间复杂度：O(n)
*/
func calculate(s string) int {
	var ans int
	stack := []int{1}
	sign := 1
	n := len(s)
	for i := 0; i < n; {
		switch s[i] {
		case ' ':
			i++
		case '+':
			sign = stack[len(stack)-1]
			i++
		case '-':
			sign = -stack[len(stack)-1]
			i++
		case '(':
			stack = append(stack, sign)
			i++
		case ')':
			stack = stack[:len(stack)-1]
			i++
		default:
			num := 0
			for ; i < n && '0' <= s[i] && s[i] <= '9'; i++ {
				num = num*10 + int(s[i]-'0')
			}
			ans += sign * num
		}
	}
	return ans
}

func main() {
	s := "(1+(4+5+2)-3)+(6+8)"
	fmt.Println(calculate(s))
}

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1
求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：
输入：heights = [2,4]
输出：4

func max(x, y int) int {
	if x > y {
		return x
	} else {
		return y
	}
}

/*
方法一：暴力法(会超出时间限制)
时间复杂度：O(N^2)
空间复杂度：O(1)

遍历每个矩形，依次向两边扩展，找到大于当前矩形高度的最左边和最右边的矩形下标，
然后计算相乘，求出最大高度（用时间换空间）
*/
func largestRectangleArea(heights []int) int {
	length := len(heights)
	if length == 0 {
		return 0
	}
	result := 0
	for i := 0; i < length; i++ {
		// 往左边找
		left, curHeight := i, heights[i]
		for left > 0 && heights[left-1] >= curHeight {
			left--
		}

		// 往右边找
		right := i
		for right < length-1 && heights[right+1] >= curHeight {
			right++
		}
		width := right - left + 1
		result = max(result, width*curHeight)
	}
	return result
}

/*
解法二：单调栈
时间复杂度：O(N)
空间复杂度：O(N)

详解参考：
https://leetcode.cn/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/
*/
func largestRectangleArea2(heights []int) int {
	length := len(heights)
	if length == 0 {
		return 0
	}
	if length == 1 {
		return heights[0]
	}
	result := 0
	newHeights := make([]int, len(heights)+2, len(heights)+2)
	for i, v := range heights {
		newHeights[i+1] = v
	}
	newHeights[0], newHeights[length+1] = 0, 0
	length += 2

	stack := make([]int, length, length)
	stack = append(stack, 0)
	for i := 1; i < length; i++ {
		for newHeights[i] < newHeights[stack[len(stack)-1]] {
			curHeight := newHeights[stack[len(stack)-1]]
			stack = stack[0 : len(stack)-1]
			curWidth := i - stack[len(stack)-1] - 1
			result = max(result, curWidth*curHeight)
		}
		stack = append(stack, i)
	}

	return result
}

func main() {
	heights := []int{2, 1, 5, 6, 2, 3}
	fmt.Println(largestRectangleArea(heights))
	fmt.Println(largestRectangleArea2(heights))
}

给定n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水（格子空隙处接雨水）。

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

题解：
https://leetcode.cn/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode-solution-tuvc/

/*
动态规划
时间复杂度：O(n)
空间复杂度：O(n)
*/
func trap1(height []int) int {
	max := func(i int, i2 int) int {
		if i < i2 {
			return i2
		}
		return i
	}
	min := func(i int, i2 int) int {
		if i < i2 {
			return i
		}
		return i2
	}
	n := len(height)
	if n == 0 {
		return 0
	}
	leftMax := make([]int, n)
	leftMax[0] = height[0]
	for i := 1; i < n; i++ {
		leftMax[i] = max(leftMax[i-1], height[i])
	}
	rightMax := make([]int, n)
	rightMax[n-1] = height[n-1]
	for i := n - 2; i >= 0; i-- {
		rightMax[i] = max(rightMax[i+1], height[i])
	}
	var ans int
	for i, v := range height {
		ans += min(leftMax[i], rightMax[i]) - v
	}
	return ans
}

/*
单调栈
时间复杂度：O(n)
空间复杂度：O(n)
*/
func trap2(height []int) int {
	min := func(i int, i2 int) int {
		if i < i2 {
			return i
		}
		return i2
	}
	var stack []int
	var ans int
	for i, v := range height {
		for len(stack) > 0 && v > height[stack[len(stack)-1]] {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				break
			}
			left := stack[len(stack)-1]
			curWidth := i - left - 1
			curHeight := min(v, height[left]) - height[top]
			ans += curWidth * curHeight
		}
		stack = append(stack, i)
	}
	return ans
}

/*
双指针
时间复杂度：O(n)
空间复杂度：O(1)
*/
func trap3(height []int) int {
	max := func(i int, i2 int) int {
		if i < i2 {
			return i2
		}
		return i
	}

	var ans int
	left, right, leftMax, rightMax := 0, len(height)-1, 0, 0
	for left < right {
		leftMax = max(leftMax, height[left])
		rightMax = max(rightMax, height[right])
		if height[left] < height[right] {
			ans += leftMax - height[left]
			left++
		} else {
			ans += rightMax - height[right]
			right--
		}
	}
	return ans
}

func main() {
	height := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
	fmt.Println(trap1(height))
	fmt.Println(trap2(height))
	fmt.Println(trap3(height))
}

给定一个仅包含0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：
输入：matrix = [['1','0','1','0','0'],['1','0','1','1','1'],['1','1','1','1','1'],['1','0','0','1','0']]
输出：6

示例 2：
输入：matrix = []
输出：0

示例 3：
输入：matrix = [['0']]
输出：0

示例 4：
输入：matrix = [['1']]
输出：1

示例 5：
输入：matrix = [['0','0']]
输出：0

题解：
https://leetcode.cn/problems/maximal-rectangle/solution/zui-da-ju-xing-by-leetcode-solution-bjlu/

/*
单调栈
时间复杂度：O(mn)
空间复杂度：O(mn)
*/
func maximalRectangle1(matrix [][]byte) int {
	min := func(i int, i2 int) int {
		if i < i2 {
			return i
		}
		return i2
	}
	max := func(i int, i2 int) int {
		if i < i2 {
			return i2
		}
		return i
	}

	var ans int
	if len(matrix) == 0 {
		return 0
	}
	m, n := len(matrix), len(matrix[0])
	left := make([][]int, m)
	for i, row := range matrix {
		left[i] = make([]int, n)
		for j, v := range row {
			if v == '0' {
				continue
			}
			if j == 0 {
				left[i][j] = 1
			} else {
				left[i][j] = left[i][j-1] + 1
			}
		}
	}
	for i, row := range matrix {
		for j, v := range row {
			if v == '0' {
				continue
			}
			width := left[i][j]
			area := width
			for k := i - 1; k >= 0; k-- {
				width = min(width, left[k][j])
				area = max(area, (i-k+1)*width)
			}
			ans = max(ans, area)
		}
	}

	return ans
}

/*
单调栈
时间复杂度：O(mn)
空间复杂度：O(mn)
*/
func maximalRectangle2(matrix [][]byte) int {
	var ans int
	max := func(i int, i2 int) int {
		if i < i2 {
			return i2
		}
		return i
	}

	if len(matrix) == 0 {
		return 0
	}
	m, n := len(matrix), len(matrix[0])
	left := make([][]int, m)
	for i, row := range matrix {
		left[i] = make([]int, n)
		for j, v := range row {
			if v == '0' {
				continue
			}
			if j == 0 {
				left[i][j] = 1
			} else {
				left[i][j] = left[i][j-1] + 1
			}
		}
	}
	for j := 0; j < n; j++ { // 对于每一列，使用基于柱状图的方法
		up := make([]int, m)
		down := make([]int, m)
		stk := []int{}
		for i, l := range left {
			for len(stk) > 0 && left[stk[len(stk)-1]][j] >= l[j] {
				stk = stk[:len(stk)-1]
			}
			up[i] = -1
			if len(stk) > 0 {
				up[i] = stk[len(stk)-1]
			}
			stk = append(stk, i)
		}
		stk = nil
		for i := m - 1; i >= 0; i-- {
			for len(stk) > 0 && left[stk[len(stk)-1]][j] >= left[i][j] {
				stk = stk[:len(stk)-1]
			}
			down[i] = m
			if len(stk) > 0 {
				down[i] = stk[len(stk)-1]
			}
			stk = append(stk, i)
		}
		for i, l := range left {
			height := down[i] - up[i] - 1
			area := height * l[j]
			ans = max(ans, area)
		}
	}
	return ans
}

func main() {
	matrix := [][]byte{
		{'1', '0', '1', '0', '0'},
		{'1', '0', '1', '1', '1'},
		{'1', '1', '1', '1', '1'},
		{'1', '0', '0', '1', '0'},
	}
	fmt.Println(maximalRectangle1(matrix))
	fmt.Println(maximalRectangle2(matrix))
}

给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值
提示：1 <= k <= nums.length

示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

示例 2：
输入：nums = [1], k = 1
输出：[1]

/*
单调队列：（队列中的值单调递增或递减）
时间复杂度：O(n)
空间复杂度：O(k)
题解：
https://leetcode.cn/problems/sliding-window-maximum/solution/dong-hua-yan-shi-dan-diao-dui-lie-239hua-hc5u/
*/
func maxSlidingWindow(nums []int, k int) []int {
	var q []int
	push := func(i int) {
		// 如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除，
		// 直到队列为空或当前考察元素小于新的队尾元素
		for len(q) > 0 && nums[i] >= nums[q[len(q)-1]] {
			q = q[:len(q)-1]
		}
		// 存储元素下标
		q = append(q, i)
	}

	// 先放入前k个元素下标
	for i := 0; i < k; i++ {
		push(i)
	}

	n := len(nums)
	// 窗口个数
	ans := make([]int, 1, n-k+1)
	ans[0] = nums[q[0]]
	for i := k; i < n; i++ {
		push(i)
		// 当队首元素的下标小于滑动窗口左侧边界时
		// 表示队首元素已经不再滑动窗口内，因此将其从队首移除
		for q[0] <= i-k {
			q = q[1:]
		}
		ans = append(ans, nums[q[0]])
	}
	return ans
}

func main() {
	nums := []int{1, 3, -1, -3, 5, 3, 6, 7}
	k := 3
	fmt.Println(maxSlidingWindow(nums, k))
}