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