提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

《算法竞赛进阶指南》0x11 栈

算法 指南 进阶 竞赛
2023-06-13 09:14:15 时间

栈的基础概念

栈的逻辑存储结构属于 “受限线性表”，其 “受限” 的部分是只能在线性表的一端执行插入和删除

栈的修改是按照 后进先出 的原则进行的，因此栈通常被称为是 后进先出（last in first out）表，简称 LIFO 表

通常，允许插入删除的一端称为 “栈顶”，不允许的一端称为 “栈底”

物理存储实现 可以在 C++ 中用一个数组和一个变量（记录栈顶位置）来实现栈存储

C++ STL 中的栈

C++ 中的 STL 也提供了一个容器 std::stack，使用前需要引入 stack 头文件

STL 中对 stack 的定义:

// clang-format off
template<
    class T,
    class Container = std::deque<T>
> class stack;

T 为 stack 中要存储的数据类型。Container 为用于存储元素的底层容器类型。

STL 容器 std::vector、std::deque 和 std::list 满足这些要求。如果不指定，则默认使用 std::deque 作为底层容器。

STL 中的 stack 容器提供了一众成员函数以供调用，其中较为常用的有：

  • 元素访问
    • st.top() 返回栈顶
  • 修改
    • st.push() 插入传入的参数到栈顶
    • st.pop() 弹出栈顶
  • 容量
    • st.empty() 返回是否为空
    • st.size() 返回元素数量

此外，std::stack 还提供了一些运算符。较为常用的是使用赋值运算符 = 为 stack 赋值

表达式求值

表达式求值是栈的一个经典应用，表达式类型分为三种：前缀、中缀、后缀表达式

后缀表达式求值

  1. 建立一个用于存数的栈，逐一扫描该后缀表达式的元素
    1. 如果遇到一个数，则把数入栈
    2. 如果遇到运算符，就取出栈顶的两个数进行计算，把结果存回栈中
  2. 扫描完成后，栈中恰好剩下一个数，就是该后缀表达式的值

中缀表达式求转后缀表达式

  1. 建立一个用于存运算符的栈，逐一扫描该中缀表达式的元素
    1. 如果遇到一个数，输出该数
    2. 如果遇到左括号，把左括号入栈
    3. 如果遇到右括号，不断取出栈顶并输出，直到栈顶为左括号，然后把左括号出栈
    4. 如果遇到运算符，只要栈顶符号的优先级不低于新符号，就不断取出栈顶并输出，最后把新符号进栈。优先级为乘除 > 加减 > 左括号
  2. 一次取出并输出栈中的所有剩余符号，最终输出的序列就是一个与原中缀表达式等价的后缀表达式
// 中缀表达式转后缀表达式，同时对后缀表达式求值 
int solve(string s) {
	nums.clear();
	ops.clear();
	int top = 0, val = 0;
	for (int i = 0; i < s.size(); i++) {
		// 中缀表达式的一个数字 
		if (s[i] >= '0' && s[i] <= '9') {
			val = val * 10 + s[i] - '0';
			if (s[i+1] >= '0' && s[i+1] <= '9') continue;
			// 后缀表达式的一个数，直接入栈 
			nums.push_back(val);
			val = 0;
		}
		// 中缀表达式的左括号 
		else if (s[i] == '(') ops.push_back(s[i]);
		// 中缀表达式的右括号 
		else if (s[i] == ')') {
			while (*ops.rbegin() != '(') {
				// 处理后缀表达式的一个运算符 
				calc(*ops.rbegin());
				ops.pop_back();
			}
			ops.pop_back();
		}
		// 中缀表达式的加减乘除号 
		else {
			while (ops.size() && grade(*ops.rbegin()) >= grade(s[i])) {
				calc(*ops.rbegin());
				ops.pop_back();
			}
			ops.push_back(s[i]);
		} 
	}
	while (ops.size()) {
		calc(*ops.rbegin());
		ops.pop_back();
	}
	// 后缀表达式栈中最后剩下的数就是答案 
	return *nums.begin();
}

中缀表达式的递归求值

目标：求解中缀表达式

S[1 \sim N]

的值 子问题：求解中缀表达式

S

的子区间表达式

S[L \sim R]

的值

  1. 在
L \sim R

中考虑没有被任何括号包含的运算符：

  1. 若存在加减号，选其中最后一个分成左右两半递归，结果相加减，返回
  2. 若存在乘除号，选其中最后一个分成左右两半递归，结果相乘除，返回

  1. 若不存在没有被任何括号包含的运算符
    1. 若首尾字符是括号，递归求解
    S[L + 1 \sim R - 1]

    ，把结果返回

    1. 否则，说明区间
    S[L \sim R]

    是一个数，直接返回数值

int calc(int l, int r)
{   // 寻找未被任何括号包含的最后一个加减号
	for (int i = r, j = 0; i >= l; i--)
    {
		if (s[i] == '(') j++;
		if (s[i] == ')') j--;
		if (j == 0 && s[i] == '+') return calc(l, i - 1) + calc(i + 1, r);
		if (j == 0 && s[i] == '-') return calc(l, i - 1) - calc(i + 1, r);
	}
	// 寻找未被任何括号包含的最后一个乘除号
	for (int i = r, j = 0; i >= l; i--) {
		if (s[i] == '(') j++;
		if (s[i] == ')') j--;
		if (j == 0 && s[i] == '*') return calc(l, i - 1) * calc(i + 1, r);
		if (j == 0 && s[i] == '/') return calc(l, i - 1) / calc(i + 1, r);
	}
	// 首尾是括号
	if (s[l] == '('&&s[r] == ')') return calc(l + 1, r - 1);
	// 是一个数
	int ans = 0;
	for (int i = l; i <= r; i++) ans = ans * 10 + s[i] - '0';
	return ans;
}

习题

包含min函数的栈

题目描述

设计一个支持 push，pop，top 等操作并且可以在O(1)时间内检索出最小元素的堆栈。

  • push(x) – 将元素 x 插入栈中
  • pop( ) – 移除栈顶元素
  • top( ) – 得到栈顶元素
  • getMin( ) – 得到栈中最小元素

数据范围

操作命令总数

[0,100]

。

样例

MinStack minStack = new MinStack();
minStack.push(-1);
minStack.push(3);
minStack.push(-4);
minStack.getMin();   --> Returns -4.
minStack.pop();
minStack.top();      --> Returns 3.
minStack.getMin();   --> Returns -1.

解析

栈本身是一个用于实现递归的辅助数据结构，所以执行退栈操作，相当于回溯到之前某个时间点的状态

因此，我们考虑用一个线性数据结构记录操作过程中，每个时间点栈中最小值的状态

该线性数据结构要支持在尾部

O(1)

时间实现插入删除，从而与模拟的栈保持同步

因此我们考虑引入第二个辅助栈，记录历史每个时刻的最小值，他需要完成

  1. 主栈插入新元素时，辅助栈维护的最小值更新为原最小值和信最小值中最小的那个
  2. 主栈弹出栈顶元素，辅助栈弹出栈顶元素，和主栈一起回到上个时刻的状态
  3. 主栈返回最小元素，辅助栈栈顶元素返回即可
class MinStack {
public:
    MinStack() {
        stkmin.push(INF);
    }
    void push(int x) {
        stkini.push(x);
        stkmin.push(min(x, getMin()));
    }
    void pop() {
        stkini.pop();
        stkmin.pop();
    }
    int top() {
        return stkini.top();
    }
    int getMin() {
        return stkmin.top();
    }
private:
    stack<int> stkini, stkmin;
    int INF = 1e9;
};

编辑器

题目描述

你将要实现一个功能强大的整数序列编辑器。

在开始时，序列是空的。

编辑器共有五种指令，如下：

1、I x，在光标处插入数值 x。 2、D，将光标前面的第一个元素删除，如果前面没有元素，则忽略此操作。 3、L，将光标向左移动，跳过一个元素，如果左边没有元素，则忽略此操作。 4、R，将光标向右移动，跳过一个元素，如果右边没有元素，则忽略次操作。 5、Q k，假设此刻光标之前的序列为

a_1,a_2,…,a_n

，输出

\max\limits_{1≤i≤k}S_i

，其中

S_i=a_1+a_2+…+a_i

。

输入格式

第一行包含一个整数 Q，表示指令的总数。

接下来 Q 行，每行一个指令，具体指令格式如题目描述。

输出格式

每一个 Q k 指令，输出一个整数作为结果，每个结果占一行。

数据范围

1≤Q≤10^6

,

|x|≤10^3

,

1≤k≤n

输入样例：

8
I 2
I -1
I 1
Q 3
L
D
R
Q 2

输出样例： 

2
3

解析

本题的特殊点，也是突破点在于，I D L R 四种操作都在光标位置处发生，并且操作完成后至多移动 1 个位置，因此也就允许了我们用受限线性表去快速操作队首队尾完成该操作

这题的进阶版，就是去掉了光标每次只能移动一步的限制，使得增删改的操作可以在任意点进行，那时就需要写一个巨难写的数据结构 — “块状链表”

根据 “始终在序列中间某个指定位置进行修改” 的性质，联想到动态中位数的 “对顶堆” 做法，不难想到类似的 “对顶栈” 做法

用左侧栈维护光标所指以及光标之前的序列，用右侧栈维护光标之后的序列

同时在光标以及光标之前的位置维护一个前缀和数字

s_i

再额外用一个栈记录前缀和数组

s_i

在任意时刻的前缀最大值，即可完成本题

int stk_l[N], stk_r[N], tt_l = 0, tt_r = 0;
int s[N], f[N] = {-INF};
void update_prefix(int t)
{
    s[tt_l] = s[tt_l - 1] + t;
    f[tt_l] = max(f[tt_l - 1], s[tt_l]);
}
int main()
{
    char op[2];
    int t, Q;
    cin >> Q;
    while (Q -- )
    {
        cin >> op;
        if (*op == 'I')
        {
            cin >> t;
            stk_l[ ++ tt_l] = t;
            update_prefix(t);
        }
        else if (*op == 'D')
        {
            if (!tt_l) continue;
            tt_l -- ;
        }
        else if (*op == 'L')
        {
            if (!tt_l) continue;
            stk_r[ ++ tt_r] = stk_l[tt_l -- ];
        }
        else if (*op == 'R')
        {
            if (!tt_r) continue;
            stk_l[ ++ tt_l] = stk_r[tt_r -- ];
            update_prefix(stk_l[tt_l]);
        }
        else
        {
            cin >> t;
            cout << f[t] << endl;
        }
    }
    return 0;
}

火车进栈

题目描述

这里有

n

列火车将要进站再出站，但是，每列火车只有

1

节，那就是车头。

这

n

列火车按

1

到

n

的顺序从东方左转进站，这个车站是南北方向的，它虽然无限长，只可惜是一个死胡同，而且站台只有一条股道，火车只能倒着从西方出去，而且每列火车必须进站，先进后出。

也就是说这个火车站其实就相当于一个栈，每次可以让右侧头火车进栈，或者让栈顶火车出站。

车站示意如图：

出站<——    <——进站
         |车|
         |站|
         |__|

现在请你按《字典序》输出前

20

种可能的出栈方案。

输入格式

输入一个整数

n

，代表火车数量。

输出格式

按照《字典序》输出前

20

种答案，每行一种，不要空格。

数据范围

1≤n≤20

输入样例：

3

输出样例：

123
132
213
231
321

解析

模拟题，模拟火车进出站的过程，至于要求字典序最小，我们就让出栈操作枚举在入栈之前即可

void dfs(int u)
{
    if (!cnt) return;
    if (path.size() == n)
    {
        for (auto &it: path) cout << it;
        cout << endl;
        cnt -- ;
        return;
    }
    //出站
    if (stk.size())
    {
        path.push_back(stk.top());
        stk.pop();
        dfs(u);
        stk.push(path.back());
        path.pop_back();
    }
    //入站
    if (u <= n)
    {
        stk.push(u);
        dfs(u + 1);
        stk.pop();
    }
}

火车进出栈问题

题目描述

一列火车

n

节车厢，依次编号为

1,2,3,…,n

。

每节车厢有两种运动方式，进栈与出栈，问

n

节车厢出栈的可能排列方式有多少种。

输入格式

输入一个整数

n

，代表火车的车厢数。

输出格式

输出一个整数

s

表示

n

节车厢出栈的可能排列方式数量。

数据范围

1≤n≤60000

输入样例：

3

输出样例：

5

解析

本题的做法很多，是一个经典的问题

第一种是爆搜

O(2^n)

，即利用上一题的递归，在输出答案的地方进行统计

第二种是递推

O(n^2)

，本题只要求计算出方案数，而非具体方案，于是可以通过递推直接进行统计

设

S_N

表示进栈顺序为

1, 2, \cdots , N

时可能的出栈序列总数，根据递推理论，将问题分解成若干类似子问题

考虑 "

1

" 这个数排在最终出栈序列中的位置，如果最后 “

1

” 这个数排在第

k

个，那么整个序列进出栈过程为：

  1. 整数
1

入栈

  1. 整数
2

~

k

这

k - 1

个数按某种顺序进出栈

  1. 整数
1

出栈，排在第

k

位

  1. 整数
k+1

~

N

这

N - k

个数按某种顺序进出栈

整个问题就变被 “

1

” 这个数划分成了 “

k-1

个数进出栈” 和 “

N - k

个数进出栈” 这两个子问题，得到递推式如下：

[ S_N = \sum_{i=1}^N (S_{i-1} \times S_{n-i}) ]

第三种是动态规划

O(n^2)

，用

f[i, j]

表示当前有

i

个数从栈中移出，有

j

个数还在栈中的方案总数

我这里状态定义和蓝书上不太一样，我个人认为这样定义比较容易接受一点

初始状态为

f[0, 0] = 1

目标状态为

f[n, 0]

状态计算根据最后一步进行递推，可能是栈中数字出栈，也可能是新数字加入栈中，有递推式：

[ f[i, j] = f[i - 1, j + 1] + f[i, j - 1] ]

第三种是组合数学

O(n)

，

n

个火车进出栈方案数等价于第

n

项 Catalan 数

求出组合数

\dfrac{\dbinom{2n}{n}}{n-1}

即为 Catalan 数第

n

项

Catalan 数简单推导

在直角坐标系中，从原点出发，令进栈为向右移动一步，出栈为向上移动一步，目的地为

(n, n)

则合法的方案应是整条路线都不越过

y=x

这条线的路径

且对于任意一条不合法的路线，都必定越过

y=x

并与

y=x+1

有交点

我们将图像从路线与

y=x+1

的第一个交点往后的图像关于

y=x+1

向上翻折，目的就变为

(n + 1, n - 1)

因此任意一条不合法路线都对应一条从原点出发到

(n + 1, n - 1)

的路线，且这是双射关系

所以合法方案数为从原点出发所有到

(n, n)

的方案数 - 所有到

(n + 1, n - 1)

的方案数

[ Catalan(n) = \dbinom{2n}{n} - \dbinom{2n}{n - 1} = \frac{1}{n - 1} \dbinom{2n}{n} ]

组合计数详细内容会在数学章节具体讲解

不想写高精度了，直接上了 py3

import math
n=int(input())
print(math.factorial(2*n)//math.factorial(n)//math.factorial(n)//(n+1))

直方图中最大的矩形

题目描述

直方图是由在公共基线处对齐的一系列矩形组成的多边形。

矩形具有相等的宽度，但可以具有不同的高度。

例如，图例左侧显示了由高度为

2,1,4,5,1,3,3

的矩形组成的直方图，矩形的宽度都为

1

：

通常，直方图用于表示离散分布，例如，文本中字符的频率。

现在，请你计算在公共基线处对齐的直方图中最大矩形的面积。

图例右图显示了所描绘直方图的最大对齐矩形。

输入格式

输入包含几个测试用例。

每个测试用例占据一行，用以描述一个直方图，并以整数

n

开始，表示组成直方图的矩形数目。

然后跟随

n

个整数

h_1，…，h_n

。

这些数字以从左到右的顺序表示直方图的各个矩形的高度。

每个矩形的宽度为

1

。

同行数字用空格隔开。

当输入用例为

n=0

时，结束输入，且该用例不用考虑。

输出格式

对于每一个测试用例，输出一个整数，代表指定直方图中最大矩形的区域面积。

每个数据占一行。

请注意，此矩形必须在公共基线处对齐。

数据范围

1≤n≤100000

,

0≤h_i≤1000000000

输入样例：

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

输出样例：

8
4000

解析

蓝书给出的解法:

如果下一个矩形的高度比上一个小，那么该矩形想利用之前的矩形一起构成较大的面积时，这块面积的高度都不可能超过该矩形自己的高度

既然没有用处，就可以把高于当前柱子的直方柱都删掉，用一个宽度累加、高度为该举行自己的高度的新矩形代替，这样就不会使后续的计算产生影响

于是我们维护的轮廓就变成了一个高度始终单调递增的矩形序列，问题就变得可解了

long long res = 0;
a[n + 1] = tt = 0;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n + 1; i ++ )
{
    if (a[i] > stk[tt]) 
    {
        stk[ ++ tt] = a[i], w[tt] = 1;
    }
    else
    {
        int width = 0;
        while (stk[tt] > a[i])
        {
            width += w[tt];
            res = max(res, (long long) width * stk[tt]);
            tt -- ;
        }
        stk[ ++ tt] = a[i], w[tt] = width + 1;
    }
}

y总的解法

这个解法思维度要求就低很多了，求以

h_i

为高度的矩形

其左侧最远应该是碰到第一个低于

h_i

的柱子，右侧同理

这样枚举出来的矩形一定是以

h_i

为高的最大矩形

因此我们对序列从左往右维护一个单调栈，求出任意点左侧第一个小于他高度的柱子下标

同理也求出右侧第一个小于他高度的柱子下标，设这两个值分别为

l_i, r_i

则显然该矩形最大面积为

S = (r_i - l_i - 1) \times h_i
a[0] = a[n + 1] = -1;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
tt = 0, q[tt] = 0;
for (int i = 1; i <= n; i ++ )
{
    while (a[i] <= a[q[tt]]) tt -- ;
    l[i] = q[tt];
    q[ ++ tt] = i;
}
tt = 0, q[tt] = n + 1;
for (int i = n; i; i -- )
{
    while (a[i] <= a[q[tt]]) tt -- ;
    r[i] = q[tt];
    q[ ++ tt] = i;
}
long long res = 0;
for (int i = 1; i <= n; i ++ )
    res = max(res, (long long) a[i] * (r[i] - l[i] - 1));

相关文章