代码随想录算法训练营 Day 42
Published:
单调栈
一维数组中要找到一个元素的左边或者右边第一个比自己大或者小的元素的位置，就可以使用单调栈。单调栈中就只需要存放索引，可以直接用索引得到所指向的元素
Q1. LeetCode 42
两种求解方式：1. 按行；2. 按列。具体思路见代码随想录
能接到雨水，说明一定有凹槽，那么就可以使用递增的单调栈（找到右侧第一个大于栈顶的元素），一共就有三种情况
- 当前元素小于栈顶元素，需要将其加入栈顶
- 当前元素等于栈顶元素，需要将栈顶元素弹出，再将当前元素入栈
- 当前元素大于栈顶元素，那么栈顶元素一定是凹槽所在，但还需要判断栈内是否有其他元素（保证左侧也有一个较高的柱子能够接雨水）。
这种方式是按行求量，所以高就是两侧柱子的较低值减去凹槽的高度，宽就是两侧柱子之间的距离
class Solution:
def trap(self, height: List[int]) -> int:
stack = [0]
res = 0
for i in range(1, len(height)):
if height[i] < height[stack[-1]]:
stack.append(i)
elif height[i] == height[stack[-1]]:
stack.pop()
stack.append(i)
else:
while stack and height[i] > height[stack[-1]]:
mid = height[stack[-1]]
stack.pop()
if stack:
right = height[i]
left = height[stack[-1]]
h = min(right, left) - mid
w = i - stack[-1] - 1
res += h * w
stack.append(i)
return res
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)
Q2. LeetCode 84
与之前问题相反，现在需要用递减的单调栈（找出左侧第一个小于栈顶的元素）。注意高度的获取方式
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
res = 0
stack = [0]
heights = [0] + heights + [0]
for i in range(1, len(heights)):
if heights[i] > heights[stack[-1]]:
stack.append(i)
elif heights[i] == heights[stack[-1]]:
stack.pop()
stack.append(i)
else:
while stack and heights[i] < heights[stack[-1]]:
h = heights[stack[-1]]
stack.pop()
if stack:
w = i - stack[-1] - 1
res = max(res, w * h)
stack.append(i)
return res
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)