DSA 问题集第四章

发表于 2026-04-17 分类于数据结构阅读次数：本文字数： 1.4k 阅读时长 ≈ 5 分钟

数据结构问题集第四章。

b) 使用一个累加器 acc，每次进入下一层逻辑前利用当前层逻辑更新 acc

把 (+,+) 改成 <，空间对于连加情况由 O (1) 到 O (n)，时间不变。

0001 const char pri[9][9] = { //优先级快查表[栈顶][当前]
0002    /*           |------------ 当 前 运 算 符 ------------|  */
0003    /*           +    -    *    /    ^    !    (    )    \0 */
0004    /*--  + */  '>', '>', '<', '<', '<', '<', '<', '>', '>',
0005    /* |  - */  '>', '>', '<', '<', '<', '<', '<', '>', '>',
0006    /* 栈 * */  '>', '>', '>', '>', '<', '<', '<', '>', '>',
0007    /* 顶 / */  '>', '>', '>', '>', '<', '<', '<', '>', '>',
0008    /* 运 ^ */  '>', '>', '>', '>', '>', '<', '<', '>', '>',
0009    /* 算 ! */  '>', '>', '>', '>', '>', '>', ' ', '>', '>',
0010    /* 符 ( */  '<', '<', '<', '<', '<', '<', '<', '~', ' ',
0011    /* |  ) */  ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ',
0012    /*-- \0 */  '<', '<', '<', '<', '<', '<', '<', ' ', '~' };

因为右括号永远不进栈。栈底 0 和右括号，栈中左括号和 0 不可能见面否则括号失配；!和 (也不会相邻。

d) 用一个极小的数值 10^-9 和浮点数比较

a) 都是从低优先级到高优先级，否则会触发计算过程

b)1+2*(1+2)

c) 不是。((((((1))))))

d)1+2*3^(1+2*+3^(…)),n/4

a) k 先出栈意味着 ij 已经先入栈了，于是 ij 相对顺序是 (j…i)

b) 同理

[0,n),如果是 stack [i] 最后进入 B 栈前面 (0,i) 自己玩自己的，而后 [i] 入中转栈然后直到最后才出去，(i,n) 自己玩自己的，$SP (n)=\sum^{n-1}_1 {SP (i)*SP (n-i-1)}$

a) b) 一样的

a)S_a 需要一直在中转栈底部，而 C 紧邻 S_a 在前面，所以 C 必须先出中转栈

b)C₄=14

c)S_b 出栈时全栈空，所以在它前面的都出栈了。由于 S_b 必须等最后出栈，所以 A 先出在 S_b 紧邻前面

d)14

e) 都是 C₃=5

f) 中间是 TDS_b 和 S_aTD 的混洗。TDS,TSD,DTS,SDT 相同 4 个，不同 1 个

g) 容斥原理：14 + 14-4 = 24 个

0001 Rank spCheck( Vector<Rank>& B ) { //B = unsort[1,n]
0002    Stack<Rank> S; Rank A = 1; //中转栈、输入栈，后者<1,2,3,...,n]只需记录栈顶
0003    for ( Rank n = B.size(), r = 0; r < n; S.pop(), r++ ) //模拟：逐项尝试B操作
0004       if ( S.empty() || S.top() != B[r] )
0005          if ( n < A  || B[r] < A ) //A已空，或者不含B[r]
0006             return r; //卡住
0007          else
0008             do { S.push( A++ ); } while ( S.top() != B[r] ); //A操作
0009    return B.size(); //成功
0010 }

如果序列合规，算法进行到第 r 步需要考查栈顶和序列当前位置。如果当前和栈顶相同就 pop 模拟中转栈出栈；如果不同说明当前需要的元素还在 A 栈里，需要不断的压栈直到栈顶和当前位置相同，出栈。

如果不合规，则有两种情况。如果 B [r]<A 说明 B [r] 比当前入栈的 A 还要小，但是入栈序列是递增的，那么说明 A 一定在之前入栈过了；n < A 说明 n 个元素都入中转栈但是还是没有栈顶。

如果合法，每个元素都需要经历入一次出一次栈，总体 O (n)。而最坏情况下 while 循环需要遍历整个序列直到在底部找到当前需要的元素, O (n)。

一次 push 等同于写下一个左括号，一次 pop 等同于写下一个右括号。

由于不能对空栈出栈，所以任何时刻入栈次数 >= 出栈次数，任何时刻左括号 >= 右括号，最后两种操作相等保证括号数相等。

0001 uint64_t mr_STACK( uint64_t H[], Rank n ) { //单趟扫描版
0002    Stack<Rank> SR; //次栈顶、栈顶总是s[r]-1与r，当前的t = t[r]
0003    uint64_t maxRect = 0;
0004    for ( Rank t = 0; t <= n; t++ ) { //对于以t为右限的
0005       while ( !SR.empty() && ( t == n || H[SR.top()] >= H[t] ) ) { //每一个极大矩形
0006          Rank r = SR.pop(), s = SR.empty() ? 0 : SR.top() + 1; //次栈顶即是左限
0007          maxRect = max( maxRect, H[r] * ( t - s ) ); //算出面积，并择优更新
0008       } //while
0009       if ( t < n ) SR.push( t ); //栈中只记录所有的H[s] = min{ H[k] | s <= k <= t }
0010    } //assert( SR.empty() )
0011    return maxRect;
0012 }