{"id":1196,"date":"2020-05-06T22:06:22","date_gmt":"2020-05-07T05:06:22","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1196"},"modified":"2020-05-25T19:36:11","modified_gmt":"2020-05-26T02:36:11","slug":"monotonic-queue-concepts","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/05\/06\/monotonic-queue-concepts\/","title":{"rendered":"Monotonic Queue Concepts"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Summary<\/h2>\n\n\n\n<p>Usually, the monotonic queue can be used in the following situations.<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li><strong>Next Greater\/Greatest<\/strong>: find the first larger or smaller element (or the largest or smallest element) from the current index to the very right index;<\/li><li><strong>Sliding Window Max<\/strong>: find the smallest or largest value in a sliding window<\/li><li><strong>Length s.t. Max<\/strong>: find the longest interval of an element so that the element is the largest or smallest value in the interval (this is essentially nearest larger, since the current number will be the maximum until it meets the nearest larger number)<\/li><\/ol>\n\n\n\n<p>Other experience is that,<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>Pop elements on one side because once the current element join in, the element poped could not be the maximum (or minimum) values later<\/li><li>Pop elements on the other side because of the invalid index (out of sliding window or poped from the normal queue)<\/li><\/ol>\n\n\n\n<p>We provide some templates for typical usage of Monotonic Queue.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">\/\/ Sliding Window from left to right\nstruct SlidingWindowMax {\n    \/\/ {index, val}\n    deque&lt;pair&lt;int, int>> dq; \n    \/\/ invalidate x where x &lt;= index\n    void remove(int index) {\n        while (dq.size() > 0 &amp;&amp; dq.front().first &lt;= index) {\n            dq.pop_front();\n        }\n    }\n    void add(int index, int val) {\n        while (dq.size() > 0 &amp;&amp; dq.back().second &lt;= val) {\n            dq.pop_back();\n        }\n        dq.push_back({index, val});\n    }\n    pair&lt;int, int> max() {\n        return dq.size() > 0 ? dq.front() : -1;\n    }\n};<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">\/\/ Sliding Window from left to right\nstruct SlidingWindowNearestHigher {\n    \/\/ {index, val}\n    deque&lt;pair&lt;int, int>> dq; \n    \/\/ invalidate x where x &lt;= index\n    void remove(int index) {\n        while (dq.size() > 0 &amp;&amp; dq.front().first &lt;= index) {\n            dq.pop_front();\n        }\n    }\n    void add(int index, int val) {\n        while (dq.size() > 0 &amp;&amp; dq.back().second &lt;= val) {\n            dq.pop_back();\n        }\n        dq.push_back({index, val});\n    }\n    pair&lt;int, int> max() {\n        return dq.size() > 0 ? dq.back() : -1;\n    }\n}; <\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Summary Usually, the monotonic queue can be used in the following situations. Next Greater\/Greatest: find the first larger or smaller element (or the largest or smallest element) from the current index to the very right index; Sliding Window Max: find the smallest or largest value in a sliding window Length s.t. Max: find the longest&#8230;<\/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],"tags":[],"class_list":["post-1196","post","type-post","status-publish","format-standard","hentry","category-alg","category-monotonic-queue"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1196","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=1196"}],"version-history":[{"count":5,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1196\/revisions"}],"predecessor-version":[{"id":1315,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1196\/revisions\/1315"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1196"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1196"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1196"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}