2762. Continuous Subarrays
這題有超多解法的
反正主要概念就是去維護subarray裡的最大最小值
(1)
用map去記錄目前的subarray每個數字出現的次數
然後每移動一次就去看subarray的最大最小值差值是不是大於2
是的話就移動左指標直到subarray的最大最小值差值小於2
然後把答案加上R-L+1(以nums[R]為結尾且符合條件的subarray數量)
就可以得到答案了
不過比較慢
(2)
用兩個monotonic stack，一個遞增(min_stack)、一個遞減(max_stack)
每移動一次就去看nums[i]的值跟min_stack[0]、max_stack[0]的差值有沒有超過2
有的話就從stack裡pop出來並記錄最後pop出來的元素的index(max_stack_index、min_stack_index)
左指標會是L=max(L,max(max_stack_index,min_stack_index)+1)
然後答案加上R-L+1
就可以得到答案了
GOLANG CODE :
type Pair struct {
idx int
val int
}
type Maxstack []Pair
type Minstack []Pair
func (ms *Maxstack) Push(node Pair) {
for len(*ms) > 0 && (*ms)[len(*ms)-1].val <= node.val {
(*ms) = (*ms)[:len(*ms)-1]
}
(*ms) = append((*ms), node)
}
func (ms *Minstack) Push(node Pair) {
for len(*ms) > 0 && (*ms)[len(*ms)-1].val >= node.val {
(*ms) = (*ms)[:len(*ms)-1]
}
(*ms) = append((*ms), node)
}
func (ms *Maxstack) findidx(val int) int {
l := -1
if len(*ms) == 0 || (*ms)[0].val-val <= 2 {
return -1
}
for len(*ms) != 0 && (*ms)[0].val-val > 2 {
l = (*ms)[0].idx
(*ms) = (*ms)[1:]
}
return l
}
func (ms *Minstack) findidx(val int) int {
l := -1
if len(*ms) == 0 || val-(*ms)[0].val <= 2 {
return -1
}
for len(*ms) != 0 && val-(*ms)[0].val > 2 {
l = (*ms)[0].idx
(*ms) = (*ms)[1:]
}
return l
}
func continuousSubarrays(nums []int) int64 {
ans := 0
l := 0
minstack, maxstack := Minstack{}, Maxstack{}
for i := 0; i < len(nums); i++ {
l1, l2 := minstack.findidx(nums[i]), maxstack.findidx(nums[i])
l = max(max(l1, l2)+1, l)
ans += i - l + 1
maxstack.Push(Pair{i, nums[i]})
minstack.Push(Pair{i, nums[i]})
}
return int64(ans)
}