Стек. Монотонный стек
Структура данных стек может использоваться вместо рекурсии, чтобы избежать переполнения стека вызовов. В качестве примера можно через стек переписать любые задачи на обход в глубину.
Также стек, как структура данных, используется для решения задач отдельных категорий, среди которых парсинг выражений, задачи на правильные скобочные последовательности и монотонный стек.
Базовые задачи
- 155. Min Stack
- 150. Evaluate Reverse Polish Notation
- 84. Largest Rectangle in Histogram
- 316. Remove Duplicate Letters
- 1047. Remove All Adjacent Duplicates In String
- 388. Longest Absolute File Path
- 636. Exclusive Time of Functions
- 946. Validate Stack Sequences
- 962. Maximum Width Ramp
- 1003. Check If Word Is Valid After Substitutions
Скобочные последовательности
- 20. Valid Parentheses
- 844. Backspace String Compare
- 1021. Remove Outermost Parentheses
- 1614. Maximum Nesting Depth of the Parentheses
- 678. Valid Parenthesis String
- 856. Score of Parentheses
- 921. Minimum Add to Make Parentheses Valid
Монотонный стек
- 402. Remove K Digits
- 456. 132 Pattern
- 496. Next Greater Element I
- 503. Next Greater Element II
- 735. Asteroid Collision
- 1475. Final Prices With a Special Discount in a Shop
- 739. Daily Temperatures
- 768. Max Chunks To Make Sorted II
- 901. Online Stock Span
- 907. Sum of Subarray Minimums