单调栈本质: 及时去掉无用数据, 保证栈中数据有序。
模板题:
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
stk = []
ans = [0] * n
for i in range(n - 1, -1, -1):
t = temperatures[i]
while stk and t >= temperatures[stk[-1]]:
stk.pop()
if stk:
ans[i] = stk[-1] - i
stk.append(i)
return ans
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
stk = []
ans = [0] * n
for i, t in enumerate(temperatures):
while stk and temperatures[stk[-1]] < t:
j = stk.pop()
ans[j] = i - j
stk.append(i)
return ans
数组的循环操作可以用模运算来实现
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
stk = []
ans = [-1] * n
for i in range(n * 2):
while stk and nums[stk[-1]] < nums[i % n]:
j = stk.pop()
ans[j] = nums[i % n]
stk.append(i % n)
return ans
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
stk = []
ans = [-1] * n
for i in range(n * 2 - 1, -1, -1):
while stk and nums[stk[-1]] <= nums[i % n]:
stk.pop()
if stk:
ans[i % n] = nums[stk[-1]]
stk.append(i % n)
return ans
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
stk = []
res = 0
for i, val in enumerate(height):
while stk and height[stk[-1]] <= val:
bottom_h = height[stk.pop()]
if not stk:
break
left = stk[-1]
dh = min(height[left], val) - bottom_h
res += dh * (i - left - 1)
stk.append(i)
return res
标签：nums,int,模型,List,stk,temperatures,ans,单调 From： https://www.cnblogs.com/zk6696/p/17840161.html