单调栈及相关题解

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

单调递增栈：

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

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;
}