/*
 * ==========================================================
 * All Patterns of Monotonic Deque / Stack in C++
 * ==========================================================
 * 1. Sliding Window Maximum
 * 2. Sliding Window Minimum
 * 3. Next Greater Element
 * 4. Next Smaller Element
 * 5. Previous Greater Element
 * 6. Previous Smaller Element
 * 7. Jump Game VI (DP + sliding window max)
 * 8. Shortest Subarray with Sum at Least K
 * 9. Constrained Subsequence Sum
 * 10. Largest Rectangle in Histogram
 * ==========================================================
 */

#include <iostream>
#include <deque>
#include <vector>
#include <climits>
using namespace std;

// ----------------------------------------------------------
// 1. Sliding Window Maximum
//    Decreasing deque -> front is the max of the window
// ----------------------------------------------------------
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;  // stores indices
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
        // Remove index if it is outside the current window
        if (!dq.empty() && dq.front() <= i - k)
            dq.pop_front();

        // Remove from back all elements smaller than current
        while (!dq.empty() && nums[dq.back()] < nums[i])
            dq.pop_back();

        dq.push_back(i);

        // The front is the maximum for the current window
        if (i >= k - 1)
            res.push_back(nums[dq.front()]);
    }
    return res;
}

// ----------------------------------------------------------
// 2. Sliding Window Minimum
//    Increasing deque -> front is the min of the window
// ----------------------------------------------------------
vector<int> minSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
        if (!dq.empty() && dq.front() <= i - k)
            dq.pop_front();

        // Remove from back all elements larger than current
        while (!dq.empty() && nums[dq.back()] > nums[i])
            dq.pop_back();

        dq.push_back(i);

        if (i >= k - 1)
            res.push_back(nums[dq.front()]);
    }
    return res;
}

// ----------------------------------------------------------
// 3. Next Greater Element (to the right)
//    Monotonic decreasing stack (using deque as stack)
// ----------------------------------------------------------
vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    deque<int> st;  // stack of indices
    for (int i = 0; i < n; i++) {
        // While current is greater than top of stack, update answer
        while (!st.empty() && nums[st.back()] < nums[i]) {
            res[st.back()] = nums[i];
            st.pop_back();
        }
        st.push_back(i);
    }
    return res;
}

// ----------------------------------------------------------
// 4. Next Smaller Element (to the right)
//    Monotonic increasing stack
// ----------------------------------------------------------
vector<int> nextSmallerElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    deque<int> st;
    for (int i = 0; i < n; i++) {
        // While current is smaller than top, update answer
        while (!st.empty() && nums[st.back()] > nums[i]) {
            res[st.back()] = nums[i];
            st.pop_back();
        }
        st.push_back(i);
    }
    return res;
}

// ----------------------------------------------------------
// 5. Previous Greater Element (to the left)
//    Monotonic decreasing stack (scan left to right)
// ----------------------------------------------------------
vector<int> previousGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    deque<int> st;
    for (int i = 0; i < n; i++) {
        // Pop elements smaller than or equal to current
        while (!st.empty() && nums[st.back()] <= nums[i])
            st.pop_back();

        // Top is the previous greater (if exists)
        if (!st.empty())
            res[i] = nums[st.back()];

        st.push_back(i);
    }
    return res;
}

// ----------------------------------------------------------
// 6. Previous Smaller Element (to the left)
//    Monotonic increasing stack
// ----------------------------------------------------------
vector<int> previousSmallerElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    deque<int> st;
    for (int i = 0; i < n; i++) {
        // Pop elements larger than or equal to current
        while (!st.empty() && nums[st.back()] >= nums[i])
            st.pop_back();

        if (!st.empty())
            res[i] = nums[st.back()];

        st.push_back(i);
    }
    return res;
}

// ----------------------------------------------------------
// 7. Jump Game VI (LeetCode 1696)
//    You jump up to k steps, max sum from start to end.
//    dp[i] = nums[i] + max(dp[i-1] ... dp[i-k])
//    Use decreasing deque to keep max dp in window.
// ----------------------------------------------------------
int maxResult(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> dp(n);
    dp[0] = nums[0];
    deque<int> dq;
    dq.push_back(0);

    for (int i = 1; i < n; i++) {
        // Remove indices outside window of size k
        if (dq.front() <= i - k)
            dq.pop_front();

        // The max dp in the window is at the front
        dp[i] = nums[i] + dp[dq.front()];

        // Maintain decreasing order of dp values
        while (!dq.empty() && dp[dq.back()] <= dp[i])
            dq.pop_back();

        dq.push_back(i);
    }
    return dp[n - 1];
}

// ----------------------------------------------------------
// 8. Shortest Subarray with Sum at Least K (LeetCode 862)
//    Use prefix sums and an increasing deque.
//    We want the smallest i < j with pref[j] - pref[i] >= k.
// ----------------------------------------------------------
int shortestSubarray(vector<int>& nums, int k) {
    int n = nums.size();
    vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; i++)
        pref[i + 1] = pref[i] + nums[i];

    deque<int> dq;
    int minLen = n + 1;
    for (int i = 0; i <= n; i++) {
        // Try to shorten the subarray from the left
        while (!dq.empty() && pref[i] - pref[dq.front()] >= k) {
            minLen = min(minLen, i - dq.front());
            dq.pop_front();
        }

        // Keep deque increasing (by prefix sum)
        while (!dq.empty() && pref[dq.back()] >= pref[i])
            dq.pop_back();

        dq.push_back(i);
    }
    return (minLen == n + 1) ? -1 : minLen;
}

// ----------------------------------------------------------
// 9. Constrained Subsequence Sum (LeetCode 1425)
//    Max sum of subsequence where |i - j| <= k.
//    dp[i] = nums[i] + max(0, max(dp[i-k] ... dp[i-1]))
//    Use decreasing deque to store dp values.
// ----------------------------------------------------------
int constrainedSubsetSum(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> dp(n);
    deque<int> dq;
    int ans = INT_MIN;
    for (int i = 0; i < n; i++) {
        // Max of previous window (or 0)
        int best = dq.empty() ? 0 : dp[dq.front()];
        dp[i] = nums[i] + max(0, best);
        ans = max(ans, dp[i]);

        // Remove index out of window
        if (!dq.empty() && dq.front() <= i - k)
            dq.pop_front();

        // Maintain decreasing order of dp
        while (!dq.empty() && dp[dq.back()] <= dp[i])
            dq.pop_back();

        // Only push if dp[i] > 0 (optional but speeds up)
        if (dp[i] > 0)
            dq.push_back(i);
    }
    return ans;
}

// ----------------------------------------------------------
// 10. Largest Rectangle in Histogram (LeetCode 84)
//     Monotonic increasing stack to find previous smaller
//     and next smaller for each bar.
// ----------------------------------------------------------
int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    deque<int> st;
    int maxArea = 0;
    for (int i = 0; i <= n; i++) {
        int curHeight = (i == n) ? 0 : heights[i];
        // Pop when a smaller height is encountered
        while (!st.empty() && heights[st.back()] > curHeight) {
            int h = heights[st.back()];
            st.pop_back();
            int width = st.empty() ? i : i - st.back() - 1;
            maxArea = max(maxArea, h * width);
        }
        st.push_back(i);
    }
    return maxArea;
}

// ----------------------------------------------------------
// Example usage
// ----------------------------------------------------------
int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    cout << "Sliding Window Maximum: ";
    for (int x : maxSlidingWindow(nums, k)) cout << x << " ";
    cout << endl;

    cout << "Sliding Window Minimum: ";
    for (int x : minSlidingWindow(nums, k)) cout << x << " ";
    cout << endl;

    vector<int> arr = {2, 1, 2, 4, 3};
    cout << "Next Greater: ";
    for (int x : nextGreaterElement(arr)) cout << x << " ";
    cout << endl;

    cout << "Previous Smaller: ";
    for (int x : previousSmallerElement(arr)) cout << x << " ";
    cout << endl;

    vector<int> heights = {2, 1, 5, 6, 2, 3};
    cout << "Largest Rectangle Area: " << largestRectangleArea(heights) << endl;

    return 0;
}