Some scenarios where a stack is typically the appropriate data structure to use:
1. Parentheses Matching: Problems that require checking for balanced parentheses or brackets often utilize stacks to ensure that every opening bracket has a corresponding closing bracket.
2. Depth-First Search (DFS): When traversing trees or graphs, a stack can be used to implement DFS iteratively, allowing you to explore nodes in a last-in, first-out manner.
3. Backtracking: In problems that require exploring all possible configurations (like permutations or combinations), stacks can help manage the state as you backtrack through different paths.
4. Next Greater Element: Problems that require finding the next greater element for each element in an array can often be solved efficiently using a stack to keep track of indices.
5. Sorting: Some sorting problems, such as sorting a stack itself, can be approached using additional stacks to hold elements temporarily.
6. Expression Evaluation: Evaluating postfix or infix expressions can be effectively handled using stacks to manage operators and operands.
7. Sliding Window Problems: In certain sliding window problems, stacks can help maintain the order of elements and efficiently compute results based on the current window.
8. History Tracking: Problems that require tracking previous states or actions (like undo functionality) can utilize stacks to store and retrieve states in a manageable way.
In summary, whenever you encounter problems that involve nested structures, require backtracking, or need to maintain a specific order of operations, consider using a stack as your primary data structure.
For the remaining types of problems, please refer to my channel.
everecursion-CSDN博客everecursion关注python,github,chatgpt领域.https://blog.csdn.net/gcsyymm?type=blog
Valid Parentheses
Valid Parentheses
https://leetcode.cn/problems/valid-parentheses/Difficulty:EZ
class Solution:
def isValid(self, s: str) -> bool:
pairs = {
"}": "{",
"]": "[",
")": "(",
}
stk = []
for c in s:
# if it is a left half; get inside stk
if c not in pairs:
stk.append(c)
else:
# it is a right half; stk is empty or mismatch
if not stk or pairs[c] != stk[-1]:
return False
stk.pop()
return not stk
Simplify Path
Simplify Pathhttps://leetcode.cn/problems/simplify-path/Difficulty:MED
class Solution:
def simplifyPath(self, path: str) -> str:
stk = []
for p in path.split("/"):
# omit all empty and .
if p == "." or not p:
continue
# it is not a ..; it is a valid dir
elif p != "..":
stk.append(p)
# if there are parent dir; pop it
elif stk:
stk.pop()
return "/" + "/".join(stk)
Min Stack
Min Stackhttps://leetcode.cn/problems/min-stack/Difficulty:MED
class MinStack:
def __init__(self):
# create the dummy item for comparison, first is val, second is min seen
self.stk = [("dummy", inf)]
def push(self, val: int) -> None:
self.stk.append((val, min(val, self.stk[-1][1])))
def pop(self) -> None:
self.stk.pop()
def top(self) -> int:
return self.stk[-1][0]
def getMin(self) -> int:
return self.stk[-1][1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
Evaluate Reverse Polish Notation
Evaluate Reverse Polish Notationhttps://leetcode.cn/problems/evaluate-reverse-polish-notation/Difficulty:MED
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for token in tokens:
# the negative number cant found with isdigit as there is a minus sign
# thus check the last chr of the token
if token[-1].isdigit():
stack.append(int(token))
else:
operand1 = stack.pop()
operand2 = stack.pop()
if token == "+":
stack.append(operand1 + operand2)
elif token == "-":
stack.append(operand2 - operand1)
elif token == "*":
stack.append(operand1 * operand2)
elif token == "/":
stack.append(
operand2 // operand1
if operand1 * operand2 > 0
else -(abs(operand2) // abs(operand1))
)
return stack.pop()
Basic Calculator
Basic Calculatorhttps://leetcode.cn/problems/basic-calculator/Difficulty:HARD(NOT THAT HARD)
class Solution:
def calculate(self, s: str) -> int:
# num record concatenate digits;
# res record current result;
# sign record current positivity;
# stk handle the parentheses
num, res, sign, stk = "", 0, 1, []
for c in s:
# record the concatenate digits until see other chr
if c.isdigit():
num += c
# update current result
elif c in "+-":
res += int(num) * sign if num else 0
# reset the num
num = ""
# update positivity
sign = 1 if c == "+" else -1
elif c == "(":
# record the result first
stk.append(res)
# then record the sign come before the parentheses
stk.append(sign)
# reset the result and positivity inside
res, sign = 0, 1
elif c == ")":
# update the result
res += int(num) * sign if num else 0
# reset the num and positivity
num = 0
sign = 1
# concatenate the result inside () with previous result
res *= stk.pop()
res += stk.pop()
# handle end
if num:
res += int(num) * sign
return res
For the remaining types of problems, please refer to my channel.
everecursion-CSDN博客everecursion关注python,github,chatgpt领域.https://blog.csdn.net/gcsyymm?type=blog