单调栈及相关题解

单调递增栈：栈中数据入栈单调递增序列(栈底到栈顶是单调递增)；
单调递减栈：栈中数据入栈单调递减序列(栈底到栈顶是单调递减)。

单调递增栈：

维护单调递增栈:遍历数组中每一个元素，执行入栈：每次入栈前先检验栈顶元素和进栈元素的大小。
如果栈空或进栈元素大于栈顶元素则直接入栈；如果进栈元素小于等于栈顶元素，则出栈，直至进栈元素大于栈顶元素。

int a[max];
int n;
stack<int>q;
for (int i = 1; i <= n; i++) {
    while (!q.empty() && a[i] <= q.top()) {
        q.pop();
    }
    q.push(a[i]);
}

单调递减栈：

维护单调递增栈:遍历数组中每一个元素，执行入栈：每次入栈前先检验栈顶元素和进栈元素的大小。
如果栈空或进栈元素小于栈顶元素则直接入栈；如果进栈元素大于等于栈顶元素，则出栈，直至进栈元素小于栈顶元素。

int a[max];
int n;
stack<int>q;
for (int i = 1; i <= n; i++) {
    while (!q.empty() && a[i] >=q.top()) {
        q.pop();
    }
    q.push(a[i]);
}

题解：

 运用单调递减栈，并用标记下标的方式来入栈，当找到一个元素大于栈顶元素时，用另外一个数组来记录栈顶元素对应的下一个最大值（此题我用的为手搓栈）

#include <stdio.h>

// 定义一个足够大的数组来模拟栈（这里假设数列元素个数不会超过1000，可根据实际情况调整）
#define MAX_SIZE 1000
int stack[MAX_SIZE];
int top = -1;

// 判断栈是否为空
int stack_empty() 
{
    return top == -1;
}

// 入栈操作
void stack_push(int element)
{
    if (top < MAX_SIZE - 1) 
    {
        stack[++top] = element;
    }
}

// 出栈操作
int stack_pop()
{
    if (!stack_empty())
    {
        return stack[top--];
    }
    return -1;  // 表示栈为空时的一种返回情况
}

// 获取栈顶元素
int stack_peek() 
{
    if (!stack_empty()) 
    {
        return stack[top];
    }
    return -1;  // 表示栈为空时的一种返回情况
}

// 求f(1...n)
void find_f(int* a, int n, int* result) 
{
    for (int i = n - 1; i >= 0; i--)
    {
        while (!stack_empty() && a[stack_peek()] <= a[i])
        {
            stack_pop();
        }
        result[i] = stack_empty() ? 0 : stack_peek() + 1;
        stack_push(i);
    }
}

int main() 
{
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i <n; i++)
        scanf("%d", &a[i]);
    int result[n];
    find_f(a, n, result);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", result[i]);
    }
    return 0;
}

 此题与上一题大致相同，都是向右查找第一个大于他的值，所以也用单调递减栈

#include <iostream>
#include<vector>
#include<stack>
#include<cstring>
using namespace std;
int a[100000], b[100000];
int n;
int main() {
	cin >> n;
	stack<int>q;
	for (int i = 0; i <n; i++) {
		cin >> a[i];
	}
	memset(b, 0, sizeof(b));
	q.push(0);
	for (int i = 1; i <= n; i++) {
		while (!q.empty() && a[i] > a[q.top()]) {
			b[q.top()] = i+1;
			q.pop();
		}
		q.push(i);
	}
	for (int i = 0; i < n; i++) {
		cout << b[i] << endl;
	}
	return 0;
}

 后缀最大值就是向后第一个大于他的值，与上两题相同，不过此处要求的是位异或和

 （此题我用的数组模拟栈，如果要换成栈的话直接将数组b改成栈即可）

#include<iostream>
using namespace std;
unsigned long long a[1000001];
int b[1000001], n;
int main() {
	scanf("%d", &n);
	int j = 0, i;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%llu", &a[i]);
		if (j == 0) {
			b[++j] = i;
			ans = ans ^ i;
		}
		else {
			if (a[i] < a[b[j]]) {
				b[++j] = i;
				ans = ans ^ i;
			}
			else {
				while (j > 0 && a[i] >= a[b[j]]) {
					ans = ans ^b[j]; 
					j--;
				}
				b[++j] = i;
				ans = ans ^ i;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

 单调递减栈，不过此处的等于要单独进行讨论，并且用结构体记录人数

#include<iostream>
#include<stack>
# define int long long
const int maxx = 1000000;
using namespace std;
int n;
struct node {
	int h, num;
}a[maxx];
long long ans;
stack<node>q;
signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].h, a[i].num = 1;
	}
		int ans = 0;
		for (int i = 1; i <= n; i++) {
		while(!q.empty() && a[i].h > q.top().h)
		{
			ans += q.top().num;
			q.pop();
		}
		if (!q.empty() && a[i].h == q.top().h)
		{
			node qwq = q.top();
			ans += q.top().num;
			q.pop();
			if (!q.empty())
				ans++;
			q.push(node{ qwq.h, qwq.num + 1 });
		}
		else
		{
			if (!q.empty())
				ans++;
			q.push(a[i]);
		}
	}
		cout << ans;
		return 0;
}