# Monotonic Queue (Pure)

## 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.

``````class MaxQueue {
public:
deque<int> q; // normal queue
deque<int> mq; // monotonic queue
MaxQueue() {

}

int max_value() {
if (q.size() == 0) {
return -1;
} else {
return mq.front();
}
}

void push_back(int value) {
q.push_back(value);
while (mq.size() > 0 && mq.back() < value) {
mq.pop_back();
}
mq.push_back(value);
}

int pop_front() {
if (q.size() == 0) {
return -1;
} else {
int val = q.front();
if (val == mq.front()) {
mq.pop_front();
}
q.pop_front();
return val;
}
}
};``````

#### LC 456. 132 Pattern

It is not difficult to get an `O(n^2)` or even an `O(nlogn)` solution: we enumerate `j`, find the largest smaller number on the right as `a_k`, find the smallest number on the left as `a_i`, and finally greedily compare `a_k & a_i`.

The `O(n)` version is tricky.

``````// find nums[i] < nums[j] > nums[k]

// O(n^3), i, j, k
// [1, 2, 3, 4]
// [3, 1, 4, 2]
//

// O(n^2)
// traverse j from right to left,
// find the largest value on the right of nums[j] and just smaller than nums[j]
// find the smallest value on the left of nums[j]

// O(n)
// a_i, a_j, a_k
//
// while (dq.size() > 0 && nums[i] < dq.front()) {a_k = max(a_k, dq.front()); dq.pop_front();}
// a_k get a value only if something is poped, which guarantees a_k will be smaller than some value a_j
//
//   a_j
//   /\   a_j'
//  /  \  /\
// a_i  \/  a_k'
//       a_k

bool find132pattern(vector<int>& nums) {
deque<int> dq;
int a_k = INT_MIN;
for (int i = nums.size() - 1; i >= 0; --i) {
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]
return true;
}
while (dq.size() > 0 && dq.front() < nums[i]) {
a_k = max(a_k, dq.front());
dq.pop_front();
}
dq.push_front(nums[i]);
}
// among all the pairs {nums[j], nums[k]}, where nums[j] > nums[k]
// if the largest nums[k] < all nums[i], no tuple exists
return false;
}``````

#### LC 1130. Minimum Cost Tree From Leaf Values

The DP version is not as hard as using Monotonic Queue. It could be found in my another post.

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.

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.

``````int mctFromLeafValues(vector<int>& arr) {
int n = arr.size();
deque<int> dq;
vector<int> right_larger(n, -1);
for (int i = n - 1; i >= 0; --i) {
// a number can be eliminated by an equal number on the right
while (dq.size() > 0 && arr[dq.front()] < arr[i]) {
dq.pop_front();
}
if (dq.size() > 0) {
right_larger[i] = dq.front();
}
dq.push_front(i);
}

vector<int> left_larger(n, -1);
dq.clear();
for (int i = 0; i < n; ++i) {
while (dq.size() > 0 && arr[dq.back()] <= arr[i]) {
dq.pop_back();
}
if (dq.size() > 0) {
left_larger[i] = dq.back();
}
dq.push_back(i);
}

int result = 0;
for (int i = 0; i < arr.size(); ++i) {
int min_larger = INT_MAX;
if (right_larger[i] != -1) {
min_larger = min(min_larger, arr[right_larger[i]]);
}
if (left_larger[i] != -1) {
min_larger = min(min_larger, arr[left_larger[i]]);
}
if (min_larger != INT_MAX) {
result += min_larger * arr[i];
}
}
return result;
}``````

#### LC 901. Online Stock Span

The problems asks for each element, find out how long it is qualified as the largest element to its left.

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.

#### LC 42. Trapping Rain Water

For each position, the trapped water is equal to `min(right_max,left_max)-height[i]`.

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.