Monotonic queue

Sliding Window Maximum

Remove K Digits

Shortest Unsorted Continuous Subarray

Next Greater Element I

Next Greater Element II

Largest Rectangle in Histogram

Best Time to Buy and Sell Stock II

Shortest Subarray with Sum at Least K

// 239. Sliding Window Maximum

```cpp
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> mq;
        vector<int> res;
        for (int i = 0; i < nums.size(); i++) {
            while (!mq.empty() && nums[mq.back()] < nums[i]) mq.pop_back();
            while (!mq.empty() && mq.front() <= i - k) mq.pop_front();
            mq.push_back(i);
            if (i >= k - 1) res.push_back(nums[mq.front()]);
        }
        return res;
    }
};
           

// 402. Remove K Digits

class Solution {
public:
    string removeKdigits(string num, int k) {
        string res = "";
        for (char c: num) {
            while (k > 0 && res.size() && res.back() > c) {
                res.pop_back();
                k--;
            }
            res.push_back(c);
        }
        
        while (k-- > 0) res.pop_back();
        
        while (!res.empty() && *res.begin() == '0') res.erase(res.begin());
        return res.empty() ? "0" : res;
    }
};
           

// 581. Shortest Unsorted Continuous Subarray

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        stack<int> st1, st2;
        int n = nums.size(), mn = n - 1, mx = 0;
        for (int i = 0; i < n; i++) {
            while (!st1.empty() && nums[st1.top()] > nums[i]) {
                mn = min(mn, st1.top());
                st1.pop();
            }
            st1.push(i);
        }
        
        for (int i = n - 1; i >= 0; i--) {
            while (!st2.empty() && nums[st2.top()] < nums[i]) {
                mx = max(mx, st2.top());
                st2.pop();
            }
            st2.push(i);
        }
       
         return mx - mn > 0 ? mx - mn + 1 : 0;  
    }
};
           

// 496. Next Greater Element I

class Solution1 {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res(nums1.size(), -1);
        unordered_map<int, int> hash;
        stack<int> st;
        for (int i = 0; i < nums1.size(); i++) hash[nums1[i]] = i;       
        for (int i = 0; i < nums2.size(); i++) {
            while (!st.empty() && nums2[st.top()] < nums2[i]) {
                int top = st.top(); st.pop();
                if  (hash.find(nums2[top]) == hash.end()) continue;
                res[hash[nums2[top]]] = nums2[i];
            }
            st.push(i);
        }
        return res;
    }
};
           

// 503. Next Greater Element II

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> twice = nums;
        int n = nums.size();
        vector<int> res(n, -1);
        twice.insert(twice.begin(), nums.begin(), nums.end());
        vector<int> ms;
       
        for (int i = 0; i < 2 * n; i++) {
            while (!ms.empty() && nums[ms.back()] < nums[i % n]) {
                res[ms.back()] = nums[i % n];
                ms.pop_back();
            }
            if (i < n) ms.push_back(i);
        }
        return res;
    }
};
           

// 556. Next Greater Element III, 和mq沒什麼關系

class Solution {
public:
    int nextGreaterElement(int n) {
        string num = to_string(n);
        int sz = num.size();
        int i = sz - 2;
        for (; i >= 0; i--) {
            if (num[i] < num[i + 1]) break;
        }
        if (i < 0) return -1;
        int j = sz - 1;
        for (; j > i; j--) {
            if (num[j] > num[i]) break;
        }
        swap(num[i], num[j]);
        string rest = num.substr(i + 1);
        sort(begin(rest), end(rest));
        if (stol(num.substr(0, i + 1) + rest) > INT_MAX) return -1;
        return stoi(num.substr(0, i + 1) + rest);
    }
};
           

// 84. Largest Rectangle in Histogram

class Solution {
public:
    // 方法1:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int i = 0, maxArea = 0, area = 0, n = heights.size();
        while (i < n) {
            if (st.empty() || heights[st.top()] < heights[i]) {
                st.push(i++);
            }
            else {
                int h = heights[st.top()]; 
                st.pop();
                if (st.empty()) area = i * h;
                else {
                    area = (i - st.top() - 1) * h;
                }
                
                if (area > maxArea) maxArea = area;
            }
        }
        
        while (!st.empty()) {            
            int h = heights[st.top()];
            st.pop();
            if (st.empty()) area = i * h;
            else {
                area = (i - st.top() - 1) * h;
            }
            
            if (area > maxArea) maxArea = area;
        }
        return maxArea;
    }
};
           

// 739. Daily Temperatures

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> st;
        int n = T.size();
        vector<int> res(n, 0);
        for (int i = 0; i < n; i++) {
            while (!st.empty() && T[st.top()] < T[i]) {
                res[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i);
        }
        return res;
    }
};
           

// 321. Create Maximum Number

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> res;
        int n1 = nums1.size(), n2 = nums2.size();
        
        // chooseing from nums1k(i), nums1k(k - i)
        for (int i = 0; i <= k; i++) {
            if (i > n1 || k - i > n2) continue;
            vector<int> nums1k = findK(nums1, i);
            vector<int> nums2k = findK(nums2, k - i);
            res = max(res, mergeK(nums1k, nums2k));
        }
        return res;
    }
    
    // monotonic stack
    vector<int> findK(vector<int> nums, int k) {
        int n = nums.size(), p = n - k;
        vector<int> res;
        for (auto num: nums) {
            while (p > 0 && !res.empty() && res.back() < num) {
                res.pop_back();
                p--;
            }
            res.push_back(num);
        }
        while (p-- > 0 && res.size()) res.pop_back();
        return res;
    }
    
    // merge two numsk
    vector<int> mergeK(vector<int> & nums1, vector<int> & nums2) {
        auto s1 = nums1.cbegin();
        auto e1 = nums1.cend();
        auto s2 = nums2.cbegin();
        auto e2 = nums2.cend();
        vector<int> res;
        while (s1 < e1 || s2 != e2) {
             res.push_back(lexicographical_compare(s1, e1, s2, e2) ? *s2++ : *s1++);
        }
        return res;
    }
    // 或者另一種寫法
    vector<int> mergeVector(vector<int> nums1, vector<int> nums2) {
        vector<int> res;
        while (!nums1.empty() || !nums2.empty()) {
            vector<int> &tmp = (nums1 > nums2) ? nums1 : nums2;
            res.push_back(tmp[0]);
            tmp.erase(tmp.begin());
        }
        return res;
    }
};
           

// 862. Shortest Subarray with Sum at Least K

class Solution1 {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int n = A.size(), result = n + 1;
        vector<int> presum(n + 1, 0);
        for (int i = 1; i < n + 1; i++) {
            presum[i] = presum[i - 1] + A[i - 1];
        }
        deque<int> monoq;
        for (int i = 0; i < n + 1; i++) {
            while (!monoq.empty() && presum[i] <= presum[monoq.back()]) {
                monoq.pop_back();
            }
            while (!monoq.empty() && presum[i] - presum[monoq.front()] >= K) {
                result = min(result, i - monoq.front());
                monoq.pop_front();
            }
            monoq.push_back(i);
        }
        return result < n + 1 ? result: -1;
    }
};