8.2. Stack - swchen1234/Algorithm GitHub Wiki

理论

实现

  • 支持操作：O(1) Push / O(1) Pop / O(1) Top

Stack的应用

  1. 用来记录当前信息
  2. 用来进行翻转
  3. 用来实现DFS
  4. 单调栈用来照左/右第一个比当前元素大/小的元素

Problems

1. 用来记录当前信息

155. Min Stack除了stack, 另min stack, 单调非增，每次stack pop出，检查是否和min stack顶端相同，若一样，min stack.pop()；add时若和min stack顶相同，仍旧加入min stack
716. Max Stack因为要实现O（lgn)，所以用heap+lazy retrieval来实现peekMax(),建立set()存还未删除的max(lazy retrieval)
895. Maximum Frequency Stackfreq[freq]=[val],以及cnt[val]来记录val当前的当前个数，用lazy removal的方法，比如freq[3]和freq[4]中都可能有val， 但cnt[va]=4， 那么freq[4]中装有最新值
2390. Removing Stars From a String删除*以及左边的字符
2296. Design a Text Editor因为要实现在当中delete，所以dynamic array不适用；解决方案：two stacks， 分别放cursor左右的内容
1381. Design a Stack With Increment Operation出来stk[]，还记录inc[], 若前k个加l, 则inc[k - 1] = l, 当pop时，若inc[-1]!=0, 则将值赋予前一个数即inc[-2]，返回stk.pop()+inc.pop()\

1.1 碰撞题

1.2 括号题

20. Valid Parenthesesif mp[closing bracket] != stk[-1]: return False
394. Decode String用cnt和stack，当读到[时将cnt压入stack, 同时压入“”,读到字母时，stack[-1]+=c
1249. Minimum Remove to Make Valid Parenthesesstack中存储待删除的括号的指数，先从左至右遍历括号，消去stack中能消去的括号指数，再从左至右遍历所有字符，若idx在stack中，则不放入res中
1047. Remove All Adjacent Duplicates In String 1541. Minimum Insertions to Balance a Parentheses String不用stack，设left, right, res， 逐个便利每个字符，分多个case加以讨论\

1.3 计算题

32. Longest Valid Parentheses用stack存储可能失效的括号的指数，没读入）,消去stack中的（, 更新答案，若stack中已经没有了(，则加入该)的指数，代表无效指数
227. Basic Calculator II用op记录上一次出现的符号，读到新符号时，对于op和prev进行处理，压入栈中;用到了"for ss in s + '+':"trick 来更方便地处理最后个数值
224. Basic Calculator用op记录上一次出现的符号，读到新符号时，对于op和prev进行处理，压入栈中；与227的区别在于多了()， 每当读到（时，压入栈中，读到)时，stack pop() 直到遇到（, 将括号中evaluate的值压入栈中
439. Ternary Expression Parserstk中存TF123456789, 逆序遍历str, 若遇到?，i-=1， 根据?之前的字符判断stk中pop出第一个还是第二个
1106. Parsing A Boolean Expression将tf&!|都放入stack中，若遇到)，逐个pop出直至&!|符号, 将evaluate的结果压入stack\

1.4 其它

636. Exclusive Time of Functions排序后压入stack中，更新stack[-1]的exclusive time, 注意start靠左，end靠右，故出来end时prevTime要+1，以便统一处理\

Maximum Frequency Stack

Brilliant! use a frequencyMap to store the element for each frequency level, and the max frequency, as well as the frequency for each word. So if 1 appears 6 times, then 1 will appear in frequencyMap[1], frequencyMap[2], up to frequencyMap[6], and each level is a stack storing the order of each element. nested-list-weight-sum-ii This dfs problem can be smartly solved by searching by level, and enqueue the next level list into the new queue, and keep adding integer to the sum, and add sum to the result for each level. So that the element add at the first level will be added to the result for each level.

2. 用来翻转

  • linked list 都可以用stack来实现reverse visit 445. Add Two Numbers II分别放入两个stack中
    143. Reorder List装入stack中，另p1指向linkedlist head, p2指向stack top, 建立新的linked list\

binary-tree-zigzag-level-order-traversal

若奇数层， 从左往右放入， 偶数层相反。

3. 用来实现DFS

4. 单调栈用来照左/右第一个比当前元素大/小的元素

4.1 以stack存最低点的指数，向左右分别延伸

907. Sum of Subarray Minimums 84. Largest Rectangle in Histogramstack中存储index， 高度单增，每读一个height[idx],pop stack并更新res=max(res, height*(i - stack[-1]-1),知道height[stack[-1]]<height[idx]；最后还有处理stack中剩余指数
85. Maximal Rectangle对每个格子算出1的高度，再对每一行用Q84的做法
2281. Sum of Total Strength of Wizards类似84的做法，对于每个值找到以其为最低点的最左/右区间端点，则总和为A[i]*(sum(A[i-k,...,i])+sum(A[i-k+1,...,i],...)为所有包含A[i]的子区间的和，化为presum相减，再进一步化为presum of presum(较为复杂，见[ref](https://leetcode.com/problems/sum-of-total-strength-of-wizards/editorial)\

739. Daily Temperatures单调减stack中存储(temp, idx)\ 901. Online Stock Span单调减stack中存储(price, idx)\ 1019. Next Greater Node In Linked List单调减stack中存储(p.val, idx)\

316. Remove Duplicate Letters单增栈，记录每个字母最后出现的指数，同时用seen表示是否已被加入栈中，对于每个字母，若栈顶字母比他大，且后面还会出现，则pop出
962. Maximum Width Ramp先遍历一遍nums， 建立递减stk, 再从nums逆序遍历，若元素大于stk[-1]，则从stk中pop出，每次pop出都更新答案
2030. Smallest K-Length Subsequence With Occurrences of a Letter类似于316, 当c>stack[-1]时，需要同时满足两种情况时从stack中pop: 1)剩余字符数>k-len(stack) 2)stack[-1]!=letter 或者剩余letter出现的次数>需要的；满足以下两种情况之一：1）letter==c 2)k-len(stack)>还需要放的letter个数\

【不懂！！】456. 132 Pattern 1762. Buildings With an Ocean View单调减栈\

496. Next Greater Element I单调减栈
503. Next Greater Element II遍历nums+nums
2940. Find Building Where Alice and Bob Can Meet对于height[a]>heigh[b]的情况建立dict[b]={height[a], qi}, 从右至左遍历building, 建立递减序列，用二分法查找height[a]的位置
1063. Number of Valid Subarrays单调栈\

【难】2355. Maximum Number of Books You Can Take

  1. 将问题看成找到分段单增1的斜线；dp[i]为取book[i]时，最大可以组成的[0:i]内的结果 \
  2. dp[i]=dp[j]+以book[i]为终点，从j开始每格增加1的累积和 \
  3. 找到j， 用stack存k, 使得book[k]-k单调增，不断pop出直至book[k]<book[i]-i，则k即为piecewise的上一个切点

300. Longest Increasing Subsequence遇到比栈顶小的元素，不pop出，而是用二分法找到其位置，replace by the smaller value
354. Russian Doll Envelopes相当于2d版的LIS, 以width排序后，若以heigh升序排，以monotonic stack存increasing height，则可能发生(3, 4), (3, 5)都被选中，故需要以heigh降序+monoStack排避免此情况.\

402. Remove K Digitswhile k > 0： 遍历nums， 维持单调栈，k -= 1, 若k > 0, 则stk=stk[:-k]；结果.lstrip('0')，若stk为空，则返回‘0’\

odd-even-jump

it is easy to think of use an odd and even dp array to memorize. To find the deterministic next step for each step, brute force need to go through all the remaining elements, the trick is to use a hash map store the A[i]: i and sort by the A[i]. Now at index i odd step, we only need to find the minimal index with key larger than A[i]. Hence, we iterate the map from the smallest key, use a mono decreasing stack stack to store the unprocessed key, meaning we haven't find a larger index for the visited A[i]s, therefore the top(right) stores the minimal index so far.