Stack and Monotonic Queue
Read this one at least 10 times…
907. Sum of Subarray Minimums
https://leetcode.com/contest/weekly-contest-102/problems/sum-of-subarray-minimums/
Sample code for this problem
class Solution:
def sumSubarrayMins(self, A: List[int]) -> int:
N = len(A)
left, right, stack = [1]*N, [1]*N, []
for i, a in enumerate(A):
while stack and stack[-1][0]>a:
left[i] += stack.pop()[1]
stack.append([a, left[i]])
stack = []
for i in range(N)[::-1]:
while stack and stack[-1][0]>=A[i]:
right[i] += stack.pop()[-1]
stack.append([A[i], right[i]])
return sum(a*l*r for a,l,r in zip(A, left, right)) % (10**9+7)901. Online Stock Span
https://leetcode.com/contest/weekly-contest-101/problems/online-stock-span/
class StockSpanner:def __init__(self):
self.stack = []def next(self, price: int) -> int:
count = 1
while self.stack and self.stack[-1][0] <= price:
count += self.stack.pop()[1]
self.stack.append([price, count])
return count
A summary about Monotonic Queue can be found here
The following question can be solved by monotonic queue:
- LC84. Largest Rectangle in Histogram
- LC239. Sliding Window Maximum
- LC739. Daily Temperatures
- LC862. Shortest Subarray with Sum at Least K
- LC901. Online Stock Span
- LC907. Sum of Subarray Minimums
856. Score of Parentheses
https://leetcode.com/problems/score-of-parentheses/More Good Stack Problems
https://leetcode.com/problems/score-of-parentheses/discuss/141777/C++JavaPython-O(1)-Space
Here are some problems that impressed me.
Good luck and have fun.
1130. Minimum Cost Tree From Leaf Values
907. Sum of Subarray Minimums
901. Online Stock Span
856. Score of Parentheses
503. Next Greater Element II
496. Next Greater Element I
84. Largest Rectangle in Histogram
42. Trapping Rain Water
This one can be done naturally by using standard stack level by level.
Critical steps:
1. replace () to 1
2. using stack to find one level (\*). Evaluate this level and append the result to stack.
3. If all levels are explored, all the evaluated results will be saved in the stack. Sum them up will be the final result.
class Solution:
def scoreOfParentheses(self, S: str) -> int:
S = S.replace("()", '1')
# "()()()" will be changed to "111", in this case, directly return len(S)
if "(" not in S:return len(S)
stack = []
for s in S:
stack.append(s)
if s==')':
temp = []
c = stack.pop()
# temp will contain all values in this level
# such as list("(1111)")
while c!="(":
temp.append(c)
c = stack.pop()
# append result from this level to stack
this_res = 2*sum(int(t) for t in temp if t not in "()")
stack.append(str(this_res))
return sum(int(st) for st in stack)
