# Golang每日一练(leetDay0028) 删除排序链表中的重复元素I\II、柱状图中最大的矩形

## 82. 删除排序链表中的重复元素 II Remove-duplicates-from-sorted-list-II

• 链表中节点数目在范围 [0, 300]
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

package main
import (
"fmt"
)
type ListNode struct {
Val  int
Next *ListNode
}
}
dummy := &ListNode{Val: 0, Next: head}
pre := dummy
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 {
for i := len(list) - 1; i >= 0; i-- {
p := &ListNode{Val: list[i]}
}
}
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})
head = build([]int{1, 1, 1, 2, 3})
}

1->2->5

2->3

package main
import (
"fmt"
)
type ListNode struct {
Val  int
Next *ListNode
}
}
}
} else {
}
}
func build(list []int) *ListNode {
for i := len(list) - 1; i >= 0; i-- {
p := &ListNode{Val: list[i]}
}
}
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})
head = build([]int{1, 1, 1, 2, 3})
}

## 83. 删除排序链表中的重复元素 Remove-duplicates-from-sorted-list

• 链表中节点数目在范围 [0, 300]
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

package main
import (
"fmt"
)
type ListNode struct {
Val  int
Next *ListNode
}
}
for cur != nil {
if pre.Val == cur.Val {
pre.Next = cur.Next
} else {
pre = cur
}
cur = cur.Next
}
}
func build(list []int) *ListNode {
for i := len(list) - 1; i >= 0; i-- {
p := &ListNode{Val: list[i]}
}
}
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, 3, 3})
}

func deleteDuplicates(head *ListNode) *ListNode {
return nil
}
for cur.Next != nil {
if cur.Val == cur.Next.Val {
cur.Next = cur.Next.Next
} else {
cur = cur.Next
}
}
}

1->2
1->2->3

package main
import (
"fmt"
)
type ListNode struct {
Val  int
Next *ListNode
}
}
}
}
func build(list []int) *ListNode {
for i := len(list) - 1; i >= 0; i-- {
p := &ListNode{Val: list[i]}
}
}
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, 3, 3})
}

## 84. 柱状图中最大的矩形 Largest-rectangle-in-histogram

• 1 <= heights.length <=10^5
• 0 <= heights[i] <= 10^4

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

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))
}

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))
}

## 🌟 每日一练刷题专栏 🌟

👍 点赞，你的认可是我坚持的动力！

🌟 收藏，你的青睐是我努力的方向！

|
2月前
|

17 0
|
27天前
【数据结构OJ题】移除链表元素

28 2
|
2月前
|
Go
【golang】golang 字符串切片排序
【golang】golang 字符串切片排序
25 1
|
1月前

21 0
|
2月前
|

【数据结构与算法 刷题系列】移除链表元素
【数据结构与算法 刷题系列】移除链表元素
24 0
|
3月前

29 1
|
2月前
|
Go
Go语言每日一练链表篇(一)
Go语言每日一练链表篇(一)
14 0
|
2月前
|

LeetCode 83题：删除排序链表中的重复元素【面试】
LeetCode 83题：删除排序链表中的重复元素【面试】
13 0
|
2月前
|

LeetCode 题目 82：删除排序链表中的重复元素 II
LeetCode 题目 82：删除排序链表中的重复元素 II
17 0
|
2月前
|

Redis第四弹，Redis实现list时候做出的优化ziplist(压缩链表，元素少的情况),可更好的节省空间list——(内部编码:quicklist)Object encoding
Redis第四弹，Redis实现list时候做出的优化ziplist(压缩链表，元素少的情况),可更好的节省空间list——(内部编码:quicklist)Object encoding
23 0