RMQ问题

RMQ(x, y) 就是询问数组 [x, y] 区间内部的最小值
例如：RMQ(0, 3) = 1, RMQ(3, 7) = 2
现在，固定询问区间的尾部，例如：RMQ(x, 7)
请思考，如下序列中最少记录几个元素，就可以满足RMQ(x, 7) 的任何需求

入队操作： 队尾入队，会把之前破坏单调性的元素都从队尾移出（维护单调性）
出队操作： 如果队首元素超出区间范围，就将元素从队首出队
元素性质： 队首元素，永远是当前维护区间的（最大/最小）值
序列中的每⼀个元素，在依次入队的过程中，每个元素都『黄』过

单调队列代码演示

void output(vector<int> &arr) {
    int n = arr.size(), len = 0
    for (int i = 0; i < n; i++) {
        len += cout.width(3), cout << i;
    }
    cout << endl;
    for (int i = 0; i < len; i++) cout << "-";
    cout << endl;
    for (int i = 0; i < n; i++) {
        len += cout.width(3), cout << arr[i];
    }
    cout << endl;
    return;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> arr;
    deque<int> q;
    for (int i = 0, a; i < n; i++) {
        cin >> a;
        arr.push_back(a);
    }
    output(arr);
    for (int i = 0; i < n; i++) {
        while (!q.empty() && arr[q.back()] > arr[i]) q.pop_back();
        q.push_back(i); // index
        if (i - q.front() == k) q.pop_front();
        cout << "[" << max(i - k + 1, 0) << ", " << i << "] = arr[" 
             << q.front() << "] = " << arr[q.front()] << endl;
    }
    return 0;
}

单调栈

问题引入： 给一个序列，求序列中，每个元素左侧，第一个小于它的元素
观察单调队列的逻辑模型，每个黄色元素左侧第一个小于它的元素， 是前⼀个黄色元素，根据入队列过程中，每⼀个元素都『黄』过， 那么将所有元素依次入队，当前元素在队列中的前⼀个元素，即是问题所求。
这种不从头部出的结构，我们叫他【单调栈】

单调递增：最近小于关系
单调递减：最近大于关系

总结：
单调队列： 擅长维护区间【最大/最小】值，最小值对应单调递增队列
单调栈： 擅长维护最近【大于/小于】关系 从左侧先⼊栈，就是维护左侧最近关系 从右侧先⼊栈，就是维护右侧最近关系

代码演示

void output(const vector<int> &arr) {
    int n = arr.size(), len = 0;
    for (int i = 0; i < n; i++) {
        len += cout.width(3), cout << i;
    }
    cout << endl;
    for (int i = 0; i < len; i++) cout << "-";
    cout << endl;
    for (int i = 0; i < n; i++) {
        len += cout.width(3), cout << arr[i];
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    vector<int> arr;
    arr.push_back(-1); // 添加哨兵到数组开头
    stack<int> s;
    for (int i = 0, a; i < n; i++) {
        cin >> a;
        arr.push_back(a);
    }
    arr.push_back(-1); // 添加哨兵到数组末尾
    vector<int> l(arr.size()), r(arr.size()); // 左右边界数组
    output(arr);

    // 计算右边界
    for (int i = 0, I = arr.size(); i < I; i++) {
        while (!s.empty() && arr[s.top()] > arr[i]) {
            r[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }

    // 计算左边界
    while (!s.empty()) s.pop();
    for (int i = arr.size() - 1; i >= 0; i--) {
        while (!s.empty() && arr[s.top()] > arr[i]) {
            l[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }

    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << "arr[" << i << "] = " << arr[i] 
             << ", right : arr[" << r[i] << "] = " << arr[r[i]] 
             << ", left : arr[" << l[i] << "] = " << arr[l[i]] 
             << endl;
    }
    return 0;
}

HZOJ-271 滑动窗口

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    deque<int> q;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < n; i++) {
        while (!q.empty() && arr[q.back()] > arr[i]) q.pop_back();
        q.push_back(i);
        if (i - q.front() == k) q.pop_front();
        if (i + 1 < k) continue;
        if (i >= k) cout << " ";
        cout << arr[q.front()];
    }
    cout << endl;
    q.clear();
    for (int i = 0; i < n; i++) {
        while (!q.empty() && arr[q.back()] < arr[i]) q.pop_back();
        q.push_back(i);
        if (i - q.front() == k) q.pop_front();
        if (i + 1 < k) continue;
        if (i >= k) cout << " ";
        cout << arr[q.front()];
    }
    cout << endl;
    return 0;
}

HZOJ-270 最大子序和

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> s(n + 1);
    deque<int> q;
    s.push_back(0);
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] += s[i - 1];
    }
    q.push_back(0);
    int ans = s[1];
    for (int i = 1; i <= n; i++) {
        ans = max(ans, s[i] - s[q.front()]);
        while (!q.empty() && s[i] < s[q.back()]) q.pop_back();
        q.push_back(i);
        if (q.front() == i - m) q.pop_front();
    }
    cout << ans << endl;
    return 0;
}

Leetcode-LCR184 设计自助结算系统

class Checkout {
public:
    queue<int>q;
    deque<int>d;
    Checkout() {}

    int get_max() {
        if(d.empty())return -1;
        return d.front();
    }

    void add(int value) {
        while(!d.empty()&&d.back()<value){
            d.pop_back();
        }
        d.push_back(value);
        q.push(value);
    }

    int remove() {
        if(q.empty())return -1;
        int ans=q.front();
        q.pop();
        if(ans==d.front()){
            d.pop_front();
        }
        return ans;
    }
};

HZOJ-264 最大矩形面积

int main() {
    long long n;
    cin>>n;
    vector<long long>arr(n+2,-1), l(n + 2), r(n + 2);//两个哨兵
    for (long long i = 1; i <= n; i++) {
        cin>>arr[i];
    }
    stack<long long> s;
    for (long long i = 1; i <= n + 1; i++){
        while(!s.empty()&&arr[i]<arr[s.top()]){
            r[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
    while (!s.empty()) s.pop();
    for (long long i = n; i >= 0; i--) {
        while (!s.empty() && arr[i] < arr[s.top()]) {
            l[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
    long long ans = 0;
    for (long long i = 1; i <= n; i++){
        long long height=arr[i];
        long long width=r[i]-l[i]-1;
        ans=max(ans,height*width);
    }
    cout<<ans;
    return 0;
}

Leetcode-1438 绝对差不超过限制的最长连续子数组

变长的滑动窗口

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        deque<int> min_q, max_q;
        min_q.push_back(0);
        max_q.push_back(0);
        int n=nums.size();
        int l=0,ans=1;
        for (int r = 1; r < n; r++) {
            while (!min_q.empty() && nums[r] < nums[min_q.back()]) min_q.pop_back();
            while (!max_q.empty() && nums[r] > nums[max_q.back()]) max_q.pop_back();
            min_q.push_back(r);
            max_q.push_back(r);
            while (nums[max_q.front()] - nums[min_q.front()] > limit) {
                if (min_q.front() == l) min_q.pop_front();
                if (max_q.front() == l) max_q.pop_front();
                l += 1;
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

Leetcode-42 接雨水

单调栈维护单调递减的序列

class Solution {
public:
    int trap(vector<int>& height) {
        int ans=0;
        stack<int>s;
        for(int i=0;i<height.size();i++){
            while(!s.empty() && height[s.top()] < height[i]){
                int h=height[s.top()];
                s.pop();
                if(s.empty())break;
                ans+=(min(height[s.top()], height[i]) - h) * (i - s.top() - 1);
            }
            s.push(i);
        }
        return ans;
    }
};

Leetcode-862 和至少为 K 的最短子数组

维护单调递增单调队列

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n=nums.size();
        vector<long long> sum(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        deque<int> q;
        q.push_back(0);
        int ans = n + 1;
        for (int i = 1; i <= n; i++) {
            while (!q.empty() && sum[i] - sum[q.front()] >= k) {
                ans = min(ans, i - q.front());
                q.pop_front();
            }
            while (!q.empty() && sum[i] < sum[q.back()]) q.pop_back();
            q.push_back(i);
        }
        if (ans == n + 1) return -1;
        return ans;
    }
};

HZOJ-372 双生序列

int main() {
    int n;
    cin>>n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) cin>>a[i];
    for (int i = 0; i < n; i++) cin>>b[i];
    deque<int>aq,bq;
    int i;
    for(i=0;i<n;i++){
        while(!aq.empty()&&a[i]<=aq.back())aq.pop_back();
        while(!bq.empty()&&b[i]<=bq.back())bq.pop_back();
        aq.push_back(a[i]);
        bq.push_back(b[i]);
        if (aq.size()!= bq.size()) break;
    }
    cout<<i;
    return 0;
}