网络问卷制作平台/厦门seo厦门起梦

单调栈算法

单调栈：单调栈中的元素满足单调递增 / 递减的条件。利用单调栈，可以找到第一个比它小/大的元素的位置。

新元素入栈前，会将栈顶破坏单调性的元素出栈，直到栈空或满足栈单调性才能加入新的元素。当元素出栈时，说明待入栈的新元素是出栈元素向后找第一个比它小/大的元素。

通常，单调栈倾向于一维数组的问题，或者是多维数组可以转化为一维数组的问题。一般存储元素索引而非元素值。

时间复杂度：O(n)，所有元素只入栈一次

代码框架：以单调递增栈为例

for i in range(n):while stack and stack[-1] > nums[i]:stack.pop()stack.append(i)

相关题目

【1】739. 每日温度

单调栈做法：典型的单调栈问题，没有任何弯弯绕绕。

class Solution:def dailyTemperatures(self, T: List[int]) -> List[int]:if not T: returnn = len(T)stack = []res = [0 for _ in range(n)]for i in range(n):while stack and T[i] > T[stack[-1]]:res[stack[-1]] = i - stack[-1]stack.pop()stack.append(i)return res

暴力做法肯定会超时：

class Solution:def dailyTemperatures(self, T: List[int]) -> List[int]:if not T: return []length = len(T)res = [0 for _ in range(length)]i, j = 0, 1for i in range(length - 1):while j < length and T[j] <= T[i]:j += 1if j == length:res[i] = 0else:res[i] = j - ii += 1j = i + 1return res

【2】42. 接雨水

单调栈做法：仔细观察可以发现，墙的高度只要满足单调递减，就一定接不到雨水；只有在出现递增的情况时，才有可能接到。所以实际上可以用一个单调递减栈来解决这个问题，只要后面的元素小于当前元素，就直接入栈，如果出现了大于的情况，表示可以结算雨水了，不断出栈计算可获得的雨水。

class Solution:def trap(self, height: List[int]) -> int:if not height: return 0n = len(height)stack, res = [], 0for i in range(n):while stack and height[i] > height[stack[-1]]:cur = stack.pop()if not stack: breakleft = stack[-1]right = ih = min(height[left], height[right]) - height[cur]res += (right - left - 1) * hstack.append(i)return res

【3】84. 柱状图中最大的矩形

单调栈做法：分析发现，在下一个柱子高度小于当前柱子高度时，就可以对前面的面积进行结算。也就是维护一个单调递增栈，每当入栈元素小于栈顶元素时，就循环出栈栈顶元素，直到满足单调性。

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:if not heights: return 0heights = [0] + heights + [0]n = len(heights)stack, area = [], 0for i in range(n):while stack and heights[stack[-1]] > heights[i]:cur = stack.pop()height = heights[cur]width = i - stack[-1] -1area = max(area, height * width)stack.append(i)return area

【4】队列的最大值

单调栈做法：维护一个双端非严格单调递减队列，当待入队元素大于当前队尾元素时，将队尾元素出队，直到满足的单调递减性质为止，这样就能保证该辅助队列的队首元素总是当前最大值。在元素出队时，判断出队元素和辅助队列的队首元素是否相同，若相同则同时出队。

class MaxQueue:def __init__(self):self.queue = collections.deque()self.assist = collections.deque()   # 辅助队列def max_value(self) -> int:if not self.assist:return -1# 非严格递减双端队列return self.assist[0]def push_back(self, value: int) -> None:self.queue.append(value)# 非严格递减双端队列while self.assist and self.assist[-1] < value:self.assist.pop()self.assist.append(value) def pop_front(self) -> int:if not self.queue:return -1cur = self.queue.popleft()if cur == self.assist[0]:self.assist.popleft()return cur# Your MaxQueue object will be instantiated and called as such:
# obj = MaxQueue()
# param_1 = obj.max_value()
# obj.push_back(value)
# param_3 = obj.pop_front()