A typical sliding window problem requires the longest or shortest subarray which satisfies certain constraints. The constraint must satisfy a monotonic property<\/strong>: as the right end of the window increases, the left end won’t decrease. <\/p>\n\n\n\n If the constrain is related to maximum or minimum, we could use Monotonic Queues, which are perfect data structures to get the sliding window maximum or minimum. <\/p>\n\n\n\n Firstly we should confirm it satisfies the monotonic property. We keep a window When right increases, if the current window When right increases, if the current window Now for every right, we need to get the leftmost left. It could be done by keeping two monotonic queues (one for max, one for min), and increase left until Summary A typical sliding window problem requires the longest or shortest subarray which satisfies certain constraints. The constraint must satisfy a monotonic property: as the right end of the window increases, the left end won’t decrease. If the constrain is related to maximum or minimum, we could use Monotonic Queues, which are perfect data structures…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,52,62],"tags":[],"class_list":["post-1142","post","type-post","status-publish","format-standard","hentry","category-alg","category-monotonic-queue","category-sliding-window"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1142","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1142"}],"version-history":[{"count":2,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1142\/revisions"}],"predecessor-version":[{"id":1194,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1142\/revisions\/1194"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1142"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1142"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1142"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Details<\/h2>\n\n\n\n
LC 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit<\/a><\/h4>\n\n\n\n
[left,right]<\/code> where left is the leftmost index which keeps the absolute diff constraint. <\/p>\n\n\n\n[left,right+1]<\/code> breaks the absolute diff constraint, the window [x,right+1] for x in [0,left-1]<\/code> can’t satisfy the diff contains since the max and min values are always in [left,right]<\/code>, which causes the diff won’t decrease. <\/p>\n\n\n\n[left,right+1]<\/code> doesn’t break the constraint, left can’t decrease since in the last run, left is the leftmost good index. <\/p>\n\n\n\nslidingMax-slidingMin<=limit<\/code>. The current[left,right]<\/code> is the longest subarray for right. <\/p>\n","protected":false},"excerpt":{"rendered":"