Re: [閒聊] 每日leetcode
2940. Find Building Where Alice and Bob Can Meet
思路
(1)如果queries[i][0]==queries[i][1]
那ans[i]=queries[i][0]
(2)
假設queries[i][0]>queries[j][0]且heights[queries[i][0]]>heights[queries[0][1]]
那ans[i]=queries[i][0]
(3)
找到heights[j]>max(heights[queries[i][0]] , heights[queries[0][1]])
且j>max(queries[i][0],queries[i][1])
假設heights的長度為n
先把所有queries[i]變成queries[i][0] < queries[i][1]的形式
將queries按照queries[i][1]的大小由大排到小
並建立increasing monotonic stack
從queries[0]開始
把heights[j](j=n-1~queries[i][1])全部push進到stack裡面
接著判斷是(1)、(2)、(3)哪一種情況，(1)、(2)就照做
(3)的話就用二分搜尋法去stack裡面找
這樣就能得到答案了
golang code:
func leftmostBuildingQueries(heights []int, queries [][]int) []int {
ans, idx := make([]int, len(queries)), make([]int, len(queries))
for key := range idx {
if queries[key][0] > queries[key][1] {
queries[key][0], queries[key][1] = queries[key][1], queries[key][0]
}
idx[key] = key
}
slices.SortFunc(idx, func(i, j int) int { return queries[j][1] - queries[i][1
] })
stack := []int{}
j := len(heights) - 1
for _, val := range idx {
x, y := queries[val][0], queries[val][1]
if y == x || heights[y] > heights[x] {
ans[val] = y
} else {
for ; j > y; j-- {
for len(stack) > 0 && heights[j] > heights[stack[len(stack)-1]] {
stack = stack[:len(stack)-1]
}
stack = append(stack, j)
}
r, l := len(stack)-1, 0
result := -1
for r >= l {
m := l + (r-l)/2
if heights[stack[m]] <= heights[x] {
r = m - 1
} else {
result = stack[m]
l = m + 1
}
}
ans[val] = result
}
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.212.10 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1734872493.A.829.html
推
12/22 21:19,
11月前
, 1F
12/22 21:19, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1218 之 1554 篇)：