单调栈

单调栈即元素从栈底到栈顶单调有序的栈，为了维护单调性，在新元素入栈时，需要将栈顶若干元素出栈。

通过将一个序列中所有元素依次送入单调栈，可以完成两个任务：

1、对序列中每个元素，找到左右侧首个“都小于/都大于”它的元素；

2、对序列中每个元素，找到以其为“最小值/最大值”的最长区间。

单调增栈

元素待入栈时，将栈顶所有大于等于它的值全部出栈，然后自己入栈，以维持栈中元素单调增的性质。

栈中每个元素的底下一个元素是其在序列中左侧第一个小于它的元素；每个元素出栈时，待入栈的元素是其在序列右侧第一个小于等于它的值。

int a[n];  // 序列
stack<int> s;  // 单调栈

for (int i = 0; i < n; i++) {
    while (!s.empty() && a[s.top()] >= a[i]) {
        int x = s.top();
        s.pop();
        if (s.empty())
            break;  // 栈为空，说明x在序列左侧找不到小于它的元素，不需要处理
        // 序列左侧第一个小于x的元素是a[s.top()]
        // 序列右侧第一个小于等于x的元素是a[i]
    }
    s.push(i);
}
// 循环结束后还有元素在栈中，但这些元素在序列右侧都找不到小于等于它的元素，不需要处理

同时得到以出栈元素为“最小值”的最长区间，区间左端点为出栈后的栈顶元素，右端点为待入栈元素（“最小值”带引号，是因为出栈元素并不是严格小于区间内在其左侧元素，而是小于等于）。

int a[n];  // 序列
stack<int> s;  // 单调栈

for (int i = 0; i < n; i++) {
    while (!s.empty() && a[s.top()] >= a[i]) {
        int x = s.top();
        s.pop();
        if (s.empty())
            // 出栈元素x的“最小值”区间是[0, i-1]
        else
            // 出栈元素x的“最小值”区间是[s.top()+1, i-1]
    }
    s.push(i);
}

while (!s.empty()) {  // 循环结束后还有元素在栈中，依次出栈进行处理
    int x = s.top();
    s.pop();
    if (s.empty())
        // 出栈元素x的“最小值”区间是[0, n-1]
    else
        // 出栈元素x的“最小值”区间是[s.top()+1, n-1]
}

单调减栈

元素待入栈时，将栈顶所有小于等于它的值全部出栈，然后自己入栈，以维持栈中元素单调减的性质。

栈中每个元素的底下一个元素是其在序列中左侧第一个大于它的元素；每个元素出栈时，待入栈的元素是其在序列右侧第一个大于等于它的值。

int a[n];  // 序列
stack<int> s;  // 单调栈

for (int i = 0; i < n; i++) {
    while (!s.empty() && a[s.top()] <= a[i]) {
        int x = s.top();
        s.pop();
        if (s.empty())
            break;  // 栈为空，说明x在序列左侧找不到大于它的元素，不需要处理
        // 序列左侧第一个大于x的元素是a[s.top()]
        // 序列右侧第一个大于等于x的元素是a[i]
    }
    s.push(i);
}
// 循环结束后还有元素在栈中，但这些元素在序列右侧都找不到大于等于它的元素，不需要处理

同时得到以出栈元素为“最大值”的最长区间，区间左端点为出栈后的栈顶元素，右端点为待入栈元素（“最大值”带引号，是因为出栈元素并不是严格大于区间内在其左侧元素，而是大于等于）。

int a[n];  // 序列
stack<int> s;  // 单调栈

for (int i = 0; i < n; i++) {
    while (!s.empty() && a[s.top()] <= a[i]) {
        int x = s.top();
        s.pop();
        if (s.empty())
            // 出栈元素x的“最大值”区间是[0, i-1]
        else
            // 出栈元素x的“最大值”区间是[s.top()+1, i-1]
    }
    s.push(i);
}

while (!s.empty()) {  // 循环结束后还有元素在栈中，依次出栈进行处理
    int x = s.top();
    s.pop();
    if (s.empty())
        // 出栈元素x的“最大值”区间是[0, n-1]
    else
        // 出栈元素x的“最大值”区间是[s.top()+1, n-1]
}

---