Re: [閒聊] 每日leetcode已回收
心焦U
哥哥 心焦U，怎麼連續兩天都是hard
85. Maximal Rectangle
有一個n*m的matrix由'1'、'0'組成
找出面積最大的長方形
該長方形的元素只能是'1'
思路:
主要的思路跟84. Largest Rectangle in Histogramt這題一樣
84題只有1個矩陣
這題要做m次
把matrix[i][j]的值改成第i列，到第ｊ個元素連續1的次數
例如:[1,1,1,0,1,1]=>[1,2,3,0,1,2]
就著就是對每一行去做第84題的解法
答案就出來了
golang code
func maximalRectangle(matrix [][]byte) int {
r := len(matrix)
c := len(matrix[0])
for i := 0; i < r; i++ {
temp := byte(0)
for j := 0; j < c; j++ {
if matrix[i][j] == '0' {
temp = 0
} else {
temp += matrix[i][j]-'0'
}
matrix[i][j] = temp
}
}
matrix = append(matrix, make([]byte, c))
ans := 0
for j := 0; j < c; j++ {
stack := make([]int, 1)
stack[0] = -1
for i := 0; i <= r; i++ {
for len(stack) > 1 && matrix[i][j] < matrix[stack[len(stack)-1]][j] {
idx := stack[len(stack)-1]
stack = stack[:len(stack)-1]
width := i - stack[len(stack)-1] - 1
area := width * int(matrix[idx][j])
ans = max(ans, area)
}
stack = append(stack, i)
}
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.138.196.238 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1712989172.A.DDA.html
推
04/13 14:20,
1年前
, 1F
04/13 14:20, 1F
→
04/13 14:21,
1年前
, 2F
04/13 14:21, 2F
推
04/13 17:08,
1年前
, 3F
04/13 17:08, 3F
討論串 (同標題文章)
完整討論串 (本文為第 115 之 1548 篇)：