楼主:
JIWP (JIWP)
2024-06-24 18:21:181438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to
Limit
给一个array nums
请回传最长的subarray的长度
该subarray里的任两个元素差值不能超过limit
思路:
sliding window，用两个index:l、r代表现在window的左右边界
建立两个monotonic stack去记录最大和最小值
当最大跟最小值超过limit时，l就往右移
记得要去维护monotonic stack里的元素，保持这些元素都在window里
这样就可以得到答案了
golang code :
func longestSubarray(nums []int, limit int) int {
maxstack, minstack := []int{}, []int{}
n, l := len(nums), 0
for i := 0; i < n; i++ {
for len(maxstack) > 0 && nums[i] > nums[maxstack[len(maxstack)-1]] {
maxstack = maxstack[:len(maxstack)-1]
}
maxstack = append(maxstack, i)
for len(minstack) > 0 && nums[i] < nums[minstack[len(minstack)-1]] {
minstack = minstack[:len(minstack)-1]
}
minstack = append(minstack, i)
if nums[maxstack[0]]-nums[minstack[0]] > limit {
for l >= maxstack[0] {
maxstack = maxstack[1:]
}
for l >= minstack[0] {
minstack = minstack[1:]
}
l++
}
}
return n - l
}