1438. 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
}