I will introduce some pure Monotonic Queue problems in this post.<\/p>\n\n\n\n
Mantain a special queue so that you can do It is not difficult to get an The The DP version is not as hard as using Monotonic Queue. It could be found in my another post<\/a>. <\/p>\n\n\n\n Think this way: two numbers merge into one number. The larger one stays and the smaller one is eliminated. For every number, it should be eliminated by the nearest larger numbers. To keep cost minimum, we choose the smaller one among two nearest larger numbers. <\/p>\n\n\n\n A trick here is that a number can be eliminated by an equal number. To avoid duplication, we could assume it can only be eliminated by an equal number on the right, but not equal numbers on the left. <\/p>\n\n\n\n The problems asks for each element, find out how long it is qualified as the largest element to its left. <\/p>\n\n\n\n Monotonic Queue could used to find out the longest subarray such that the current element is the largest\/smallest. It could be easily transformed into finding the Nearest Higher\/Lower. <\/p>\n\n\n\n For each position, the trapped water is equal to Monotonic Queue could used to find out the next greatest element. Different from the next higher, we use the other side of the double ended list. <\/p>\n","protected":false},"excerpt":{"rendered":" Summary I will introduce some pure Monotonic Queue problems in this post. Details Sword to Offers Problem 59 Max Queue Mantain a special queue so that you can do max_value, push_back, and pop_front in amortized O(1) time. LC 456. 132 Pattern It is not difficult to get an O(n^2) or even an O(nlogn) solution: we…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[52],"tags":[],"class_list":["post-800","post","type-post","status-publish","format-standard","hentry","category-monotonic-queue"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/800","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=800"}],"version-history":[{"count":13,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/800\/revisions"}],"predecessor-version":[{"id":1285,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/800\/revisions\/1285"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=800"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=800"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=800"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}max_value<\/code>, push_back<\/code>, and pop_front<\/code> in amortized O(1)<\/code> time.<\/p>\n\n\n\nclass MaxQueue {\npublic:\n deque<int> q; \/\/ normal queue\n deque<int> mq; \/\/ monotonic queue\n MaxQueue() {\n \n }\n \n int max_value() {\n if (q.size() == 0) {\n return -1;\n } else {\n return mq.front();\n }\n }\n \n void push_back(int value) {\n q.push_back(value);\n while (mq.size() > 0 && mq.back() < value) {\n mq.pop_back();\n }\n mq.push_back(value);\n }\n \n int pop_front() {\n if (q.size() == 0) {\n return -1;\n } else {\n int val = q.front();\n if (val == mq.front()) {\n mq.pop_front(); \n }\n q.pop_front();\n return val;\n }\n }\n};<\/code><\/pre>\n\n\n\nLC 456. 132 Pattern<\/a> <\/h4>\n\n\n\n
O(n^2)<\/code> or even an O(nlogn)<\/code> solution: we enumerate j<\/code>, find the largest smaller number on the right as a_k<\/code>, find the smallest number on the left as a_i<\/code>, and finally greedily compare a_k & a_i<\/code>.<\/p>\n\n\n\nO(n)<\/code> version is tricky. <\/p>\n\n\n\n\/\/ find nums[i] < nums[j] > nums[k]\n\n\/\/ O(n^3), i, j, k\n\/\/ [1, 2, 3, 4]\n\/\/ [3, 1, 4, 2]\n\/\/ \n\n\/\/ O(n^2)\n\/\/ traverse j from right to left, \n\/\/ find the largest value on the right of nums[j] and just smaller than nums[j]\n\/\/ find the smallest value on the left of nums[j]\n\n\/\/ O(n)\n\/\/ a_i, a_j, a_k\n\/\/ \n\/\/ while (dq.size() > 0 && nums[i] < dq.front()) {a_k = max(a_k, dq.front()); dq.pop_front();} \n\/\/ a_k get a value only if something is poped, which guarantees a_k will be smaller than some value a_j\n\/\/\n\/\/ a_j \n\/\/ \/\\ a_j' \n\/\/ \/ \\ \/\\ \n\/\/ a_i \\\/ a_k'\n\/\/ a_k\n\nbool find132pattern(vector<int>& nums) {\n deque<int> dq;\n int a_k = INT_MIN;\n for (int i = nums.size() - 1; i >= 0; --i) {\n if (nums[i] < a_k) { \/\/ a_k got popped iif there is a number nums[j] > nums[k], k > j since nums[k] is pushed first, thus we find nums[i] < nums[j] > nums[k]\n return true;\n }\n while (dq.size() > 0 && dq.front() < nums[i]) {\n a_k = max(a_k, dq.front()); \n dq.pop_front();\n }\n dq.push_front(nums[i]);\n }\n \/\/ among all the pairs {nums[j], nums[k]}, where nums[j] > nums[k]\n \/\/ if the largest nums[k] < all nums[i], no tuple exists\n return false;\n}<\/code><\/pre>\n\n\n\nLC 1130. Minimum Cost Tree From Leaf Values<\/a> <\/h4>\n\n\n\n
int mctFromLeafValues(vector<int>& arr) {\n int n = arr.size();\n deque<int> dq;\n vector<int> right_larger(n, -1);\n for (int i = n - 1; i >= 0; --i) {\n\/\/ a number can be eliminated by an equal number on the right\n while (dq.size() > 0 && arr[dq.front()] < arr[i]) {\n dq.pop_front();\n }\n if (dq.size() > 0) {\n right_larger[i] = dq.front();\n }\n dq.push_front(i);\n }\n\n vector<int> left_larger(n, -1);\n dq.clear();\n for (int i = 0; i < n; ++i) {\n while (dq.size() > 0 && arr[dq.back()] <= arr[i]) {\n dq.pop_back();\n }\n if (dq.size() > 0) {\n left_larger[i] = dq.back();\n }\n dq.push_back(i);\n }\n\n int result = 0;\n for (int i = 0; i < arr.size(); ++i) {\n int min_larger = INT_MAX;\n if (right_larger[i] != -1) {\n min_larger = min(min_larger, arr[right_larger[i]]);\n }\n if (left_larger[i] != -1) {\n min_larger = min(min_larger, arr[left_larger[i]]);\n }\n if (min_larger != INT_MAX) {\n result += min_larger * arr[i];\n }\n }\n return result;\n}<\/code><\/pre>\n\n\n\nLC 901. Online Stock Span<\/a><\/h4>\n\n\n\n
LC 42. Trapping Rain Water<\/a><\/h4>\n\n\n\n
min(right_max,left_max)-height[i]<\/code>.<\/p>\n\n\n\n