OPEN17的个人小站
基算精讲(26)单调栈
本质思想
及时去掉无用的数据,保持栈中数据有序
视频链接
算法基础精讲
那些算法究竟是怎么想出来的？灵神将带你知其然，更知其所以然！
练习
每日温度
链接
可以说是模板题,两个角度本质是一样的,取决于st数组留的是找到NGE的还是没找到NGE的
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
l=len(temperatures)
res=[0]*l
stack=[]
for i in range(l):
while stack and temperatures[stack[-1]]<temperatures[i]:
res[stack[-1]]=i-stack[-1]
stack.pop()
stack.append(i)
return res
接雨水
链接
单调栈只能处理两个之间吗?这题学会变通
class Solution:
def trap(self, height: List[int]) -> int:
st=[]
ans=0
for idx,i in enumerate(height):
while st and height[st[-1]]<i:
h=st.pop()
if not len(st):
break
l=st[-1]
ans+=(min(height[l],i)-height[h])*(idx-l-1)
st.append(idx)
return ans
商品折扣后的最终价格
简单的运用
class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:
st=[]
for i,p in enumerate(prices):
while st and p<=prices[st[-1]]:
prices[st.pop()]-=p
st.append(i)
return prices
股票价格跨度
链接
灵神写的太妙啦,牢记及时排除不需要的数据
class StockSpanner:
def __init__(self):
self.st=[(-1,inf)]
self.cur=-1
def next(self, price: int) -> int:
while price>=self.st[-1][1]:
self.st.pop()
self.cur+=1
self.st.append((self.cur,price))
return self.cur-self.st[-2][0]
链表中的下一个更大节点
在链表上,差不了多少
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
ans=[0]*(10**4)
st=[]
cur=0
while head:
while st and st[-1][1]<head.val:
ans[st.pop()[0]]=head.val
st.append([cur,head.val])
cur+=1
head=head.next
return ans[:cur]
队列中可以看到的人数
真妙啊,要仔细审题
还有配图好抽象
class Solution:
def canSeePersonsCount(self, heights: List[int]) -> List[int]:
st=[]
ans=[0]*len(heights)
for i in range(len(heights)-1,-1,-1):
while st and st[-1]<heights[i]:
st.pop()
ans[i]+=1
if st: ans[i]+=1
st.append(heights[i])
return ans
柱状图中最大的矩形
非常好的一题,关键点是维护左右边界,贡献法思考不需要的元素,单调栈及时维护排除,哨兵优化边界
三叶姐在这里有一个很有趣的切入角度:
最终矩形的高度必然取自某个 hs[i]，因此我们可以枚举最终矩形的高度来做。
所以需要枚举高度和对应的左右边界
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
ans=0
st=[0]
# 维护左右边界,贡献法思考不需要的元素,单调栈维护排除
heights=[-1]+heights+[-1]
for i,h in enumerate(heights):
while heights[st[-1]]>h:
hi=heights[st.pop()]
ldx=st[-1]
rdx=i
ans=max(ans,hi*(rdx-ldx-1))
st.append(i)
return ans
最大矩形
链接
太妙了,对于每一行视为底的话就是柱状图中最大的矩形啊,所以我们dp预处理一下以每一行为底时的高度(如果是0便清零,贡献法思考),然后复用上一题的代码即可
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
ans=0
st=[0]
# 维护左右边界,贡献法思考不需要的元素,单调栈维护排除
heights=[-1]+heights+[-1]
for i,h in enumerate(heights):
while heights[st[-1]]>h:
hi=heights[st.pop()]
ldx=st[-1]
rdx=i
ans=max(ans,hi*(rdx-ldx-1))
st.append(i)
return ans
def maximalRectangle(self, matrix: List[List[str]]) -> int:
ans=0
n=len(matrix)
m=len(matrix[0])
dp=[[0 for _ in range(m+1)] for _ in range(n+1)]
for i,v in enumerate(matrix):
for j,vv in enumerate(v):
if vv=="1":
dp[i+1][j+1]=dp[i][j+1]+1
else:
try:
dp[i+1][j+1]=0
except:
print(i,j)
res=self.largestRectangleArea(dp[i+1])
ans=max(ans,res)
return ans
更多
单调栈总结
- 两种写法的本质就是数组维护的是未找到NGE的还是找到NGE的
- 及时去掉无用的数据,保持栈中数据有序
- 不一定只是两个之间先关的,学会变通
- 尝尝结合贡献法思考