单调栈

单调栈的”一栈两用“。 对数组从左至右维护严格单调递增栈需要不断移除栈顶元素直到栈顶元素小于待入栈元素。在这个过程中待入栈元素是移除元素右侧第一个小于等于自身的元素。在移除过程结束后，栈顶元素是待入栈元素的左侧第一个小于自身的元素。这样一个从左至右严格单调递增栈可以获得每个元素左侧第一个小于自身的元素以及每个元素右侧第一个小于等于自身的元素。

从左至右严格单调递增栈可以获得每个元素左侧第一个小于自身的元素以及每个元素右侧第一个小于等于自身的元素。 从左至右单调非减栈可以获得每个元素左侧第一个小于等于自身的元素以及每个元素右侧第一个小于自身的元素。 从左至右严格单调递减栈可以获得每个元素左侧第一个大于自身的元素以及每个元素右侧第一个大于等于自身的元素。 从左至右单调非增栈可以获得每个元素左侧第一个大于等于自身的元素以及每个元素右侧第一个大于自身的元素。

从左至右维护单调栈可以解决所有需求，然后跟增有关的栈得到左右小于或小于等于自身的值，而减有关的栈得到左右大于/大于等于自身的值。总之在从左至右前提下，增小减大。

int main() {
    vector<int> v{1,1,2,3,3,2,1,1,2,2,3};
    int n = v.size();
    cout << "index "; for (int i=0; i<n; i++) cout << i << " "; cout << endl;
    cout << "val "; for (int i:v) cout << i << " "; cout << endl;
    vector<int> st;
    vector<int> l_g(n, -1), r_ge(n, n);
    for (int i=0; i<n; i++) {
        while (st.size() && v[st.back()] <= v[i]) {//严减
            r_ge[st.back()] = i;
            st.pop_back();
        }
        if(st.size()) l_g[i] = st.back();
        st.push_back(i);
    }
    cout << "l_g "; for (int i:l_g) cout << i << " "; cout << endl;
    cout << "r_ge "; for (int i:r_ge) cout << i << " "; cout << endl;
    
    st.clear();
    vector<int> l_ge(n, -1), r_g(n, n);
    for (int i=0; i<n; i++) {
        while (st.size() && v[st.back()] < v[i]) {//非增
            r_g[st.back()] = i;
            st.pop_back();
        }
        if(st.size()) l_ge[i] = st.back();
        st.push_back(i);
    }
    cout << "l_ge "; for (int i:l_ge) cout << i << " "; cout << endl;
    cout << "r_g "; for (int i:r_g) cout << i << " "; cout << endl;
    
    st.clear();
    vector<int> l_l(n, -1), r_le(n, n);
    for (int i=0; i<n; i++) {
        while (st.size() && v[st.back()] >= v[i]) {//严增
            r_le[st.back()] = i;
            st.pop_back();
        }
        if(st.size()) l_l[i] = st.back();
        st.push_back(i);
    }
    cout << "l_l "; for (int i:l_l) cout << i << " "; cout << endl;
    cout << "r_le "; for (int i:r_le) cout << i << " "; cout << endl;
    
    st.clear();
    vector<int> l_le(n, -1), r_l(n, n);
    for (int i=0; i<n; i++) {
        while (st.size() && v[st.back()] > v[i]) {//非减
            r_l[st.back()] = i;
            st.pop_back();
        }
        if(st.size()) l_le[i] = st.back();
        st.push_back(i);
    }
    cout << "l_le "; for (int i:l_le) cout << i << " "; cout << endl;
    cout << "r_l "; for (int i:r_l) cout << i << " "; cout << endl;
    return 0;          
}
index 0 1 2 3 4 5 6 7 8 9 10
val 1 1 2 3 3 2 1 1 2 2 3
l_g -1 -1 -1 -1 -1 4 5 5 4 4 -1
r_ge 1 2 3 4 10 8 7 8 9 10 11
l_ge -1 0 -1 -1 3 4 5 6 5 8 4
r_g 2 2 3 11 11 10 8 8 10 10 11
l_l -1 -1 1 2 2 1 -1 -1 7 7 9
r_le 1 6 5 4 5 6 7 11 9 11 11
l_le -1 0 1 2 3 2 1 6 7 8 9
r_l 11 11 6 5 5 6 11 11 11 11 11

单调队列模板

//leetcode 1696. 跳跃游戏 VI
for (int i=0; i<n; i++) {
    while (que.size() && que.front()+k<i) que.pop_front();
    dp[i] = nums[i];
    if (que.size()) dp[i] += dp[que.front()];
    while (que.size() && dp[que.back()]<dp[i]) que.pop_back();
    que.push_back(i);
}

第一个while 保证队列内元素与当前位置距离小于等于k

第二个while移除小于当前待入栈元素保证队列单调非增

关于静态区间的最值问题

如果我们离线处理，发现每个区间$[l,r]$的下一个区间$[l’,r’]$