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.