82. 删除排序链表中的重复元素 II Remove-duplicates-from-sorted-list-II
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
代码1：双指针
package main import ( "fmt" ) type ListNode struct { Val int Next *ListNode } func removeDuplicates(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } dummy := &ListNode{Val: 0, Next: head} pre := dummy cur := head for cur != nil { if cur.Next != nil && cur.Val == cur.Next.Val { // 相同节点一直跳过 for cur.Next != nil && cur.Val == cur.Next.Val { cur = cur.Next } pre.Next = cur.Next } else { pre = pre.Next } cur = cur.Next } return dummy.Next } func build(list []int) *ListNode { head := &ListNode{Val: 0} for i := len(list) - 1; i >= 0; i-- { p := &ListNode{Val: list[i]} p.Next = head.Next head.Next = p } return head } func (head *ListNode) travel() { for p := head.Next; p != nil; p = p.Next { fmt.Print(p.Val) if p.Next != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { head := build([]int{1, 2, 3, 3, 4, 4, 5}) removeDuplicates(head).travel() head = build([]int{1, 1, 1, 2, 3}) removeDuplicates(head).travel() }
输出：
1->2->5
2->3
代码2：递归法
package main import ( "fmt" ) type ListNode struct { Val int Next *ListNode } func removeDuplicates(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } if head.Val == head.Next.Val { for head.Next != nil && head.Val == head.Next.Val { head = head.Next } return removeDuplicates(head.Next) } else { head.Next = removeDuplicates(head.Next) return head } } func build(list []int) *ListNode { head := &ListNode{Val: 0} for i := len(list) - 1; i >= 0; i-- { p := &ListNode{Val: list[i]} p.Next = head.Next head.Next = p } return head } func (head *ListNode) travel() { for p := head.Next; p != nil; p = p.Next { fmt.Print(p.Val) if p.Next != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { head := build([]int{1, 2, 3, 3, 4, 4, 5}) removeDuplicates(head).travel() head = build([]int{1, 1, 1, 2, 3}) removeDuplicates(head).travel() }
83. 删除排序链表中的重复元素 Remove-duplicates-from-sorted-list
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2]
输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
代码1：双指针
package main import ( "fmt" ) type ListNode struct { Val int Next *ListNode } func deleteDuplicates(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } pre := head cur := head.Next for cur != nil { if pre.Val == cur.Val { pre.Next = cur.Next } else { pre = cur } cur = cur.Next } return head } func build(list []int) *ListNode { head := &ListNode{Val: 0} for i := len(list) - 1; i >= 0; i-- { p := &ListNode{Val: list[i]} p.Next = head.Next head.Next = p } return head } func (head *ListNode) travel() { for p := head.Next; p != nil; p = p.Next { fmt.Print(p.Val) if p.Next != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { head := build([]int{1, 1, 2}) deleteDuplicates(head).travel() head = build([]int{1, 1, 2, 3, 3}) deleteDuplicates(head).travel() }
双指针另一种写法：
func deleteDuplicates(head *ListNode) *ListNode { if head == nil { return nil } cur := head for cur.Next != nil { if cur.Val == cur.Next.Val { cur.Next = cur.Next.Next } else { cur = cur.Next } } return head } 输出： 1->2 1->2->3
代码2：递归法
递归处理子链表，如果子链表的头节点和下一个节点的值相等，则将头节点的 next 指针指向下一个节点的下一个节点，这样就可以删除重复节点。
package main import ( "fmt" ) type ListNode struct { Val int Next *ListNode } func deleteDuplicates(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } head.Next = deleteDuplicates(head.Next) if head.Val == head.Next.Val { return head.Next } return head } func build(list []int) *ListNode { head := &ListNode{Val: 0} for i := len(list) - 1; i >= 0; i-- { p := &ListNode{Val: list[i]} p.Next = head.Next head.Next = p } return head } func (head *ListNode) travel() { for p := head.Next; p != nil; p = p.Next { fmt.Print(p.Val) if p.Next != nil { fmt.Print("->") } } fmt.Println("<nil>") } func main() { head := build([]int{1, 1, 2}) deleteDuplicates(head).travel() head = build([]int{1, 1, 2, 3, 3}) deleteDuplicates(head).travel() }
84. 柱状图中最大的矩形 Largest-rectangle-in-histogram
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
提示：
1 <= heights.length <=10^50 <= heights[i] <= 10^4
代码1： 暴力枚举
package main import "fmt" func largestRectangleArea(heights []int) int { n := len(heights) maxArea := 0 for i := 0; i < n; i++ { left, right := i, i for left >= 0 && heights[left] >= heights[i] { left-- } for right < n && heights[right] >= heights[i] { right++ } area := heights[i] * (right - left - 1) if area > maxArea { maxArea = area } } return maxArea } func main() { heights := []int{2, 1, 5, 6, 2, 3} fmt.Println(largestRectangleArea(heights)) heights = []int{2, 4} fmt.Println(largestRectangleArea(heights)) }
输出：
10
4
代码2： 单调栈
package main import "fmt" func largestRectangleArea(heights []int) int { n := len(heights) stack := make([]int, 0) maxArea := 0 for i := 0; i <= n; i++ { var curHeight int if i == n { curHeight = 0 } else { curHeight = heights[i] } for len(stack) > 0 && curHeight < heights[stack[len(stack)-1]] { h := heights[stack[len(stack)-1]] stack = stack[:len(stack)-1] var w int if len(stack) == 0 { w = i } else { w = i - stack[len(stack)-1] - 1 } area := h * w if area > maxArea { maxArea = area } } stack = append(stack, i) } return maxArea } func main() { heights := []int{2, 1, 5, 6, 2, 3} fmt.Println(largestRectangleArea(heights)) heights = []int{2, 4} fmt.Println(largestRectangleArea(heights)) }
代码3： 分治法
package main import "fmt" func largestRectangleArea(heights []int) int { return helper(heights, 0, len(heights)-1) } func helper(heights []int, left, right int) int { if left > right { return 0 } minIndex := left for i := left; i <= right; i++ { if heights[i] < heights[minIndex] { minIndex = i } } area1 := heights[minIndex] * (right - left + 1) area2 := helper(heights, left, minIndex-1) area3 := helper(heights, minIndex+1, right) return max(area1, max(area2, area3)) } func max(a, b int) int { if a > b { return a } return b } func main() { heights := []int{2, 1, 5, 6, 2, 3} fmt.Println(largestRectangleArea(heights)) heights = []int{2, 4} fmt.Println(largestRectangleArea(heights)) }
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
