leetcode单调栈

739. 每日温度

请���据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数

class Solution:    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:        answer = [0]*len(temperatures)        stack = [0]        for i in range(1,len(temperatures)):            # 情况一和情况二            if temperatures[i]temperatures[stack[-1]]:                    answer[stack[-1]]=i-stack[-1]                    stack.pop()                stack.append(i)        return answer

496.下一个更大元素 I

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例 1:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].

输出: [-1,3,-1]

解释:

对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。

对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。

对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

示例 2:

输入: nums1 = [2,4], nums2 = [1,2,3,4].

输出: [3,-1]

解释:

对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。

对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出-1 。

提示：

1 rHight: rHight = height[k] res1 = min(lHight,rHight) - height[i] if res1 > 0: res += res1 return res双指针：class Solution: def trap(self, height: List[int]) -> int: leftheight, rightheight = [0]*len(height), [0]*len(height) leftheight[0]=height[0] for i in range(1,len(height)): leftheight[i]=max(leftheight[i-1],height[i]) rightheight[-1]=height[-1] for i in range(len(height)-2,-1,-1): rightheight[i]=max(rightheight[i+1],height[i]) result = 0 for i in range(0,len(height)): summ = min(leftheight[i],rightheight[i])-height[i] result += summ return result单调栈class Solution: def trap(self, height: List[int]) -> int: # 单调栈 ''' 单调栈是按照 行 的方向来计算雨水 从栈顶到栈底的顺序：从小到大 通过三个元素来接水：栈顶，栈顶的下一个元素，以及即将入栈的元素 雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度 雨水的宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度） ''' # stack储存index，用于计算对应的柱子高度 stack = [0] result = 0 for i in range(1, len(height)): # 情况一 if height[i] height[stack[-1]]: # 栈顶就是中间的柱子：储水槽，就是凹槽的地步 mid_height = height[stack[-1]] stack.pop() if stack: right_height = height[i] left_height = height[stack[-1]] # 两侧的较矮一方的高度 - 凹槽底部高度 h = min(right_height, left_height) - mid_height # 凹槽右侧下标 - 凹槽左侧下标 - 1: 只求中间宽度 w = i - stack[-1] - 1 # 体积：高乘宽 result += h * w stack.append(i) return result# 单调栈压缩版class Solution: def trap(self, height: List[int]) -> int: stack = [0] result = 0 for i in range(1, len(height)): while stack and height[i] > height[stack[-1]]: mid_height = stack.pop() if stack: # 雨水高度是 min(凹槽左侧高度, 凹槽右侧高度) - 凹槽底部高度 h = min(height[stack[-1]], height[i]) - height[mid_height] # 雨水宽度是 凹槽右侧的下标 - 凹槽左侧的下标 - 1 w = i - stack[-1] - 1 # 累计总雨水体积 result += h * w stack.append(i) return result

84.柱状图中最大的矩形

力扣题目链接(opens new window)

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

1 = heights[i]: # 当左侧的柱子持续较高时，尝试这个高柱子自己的次级柱子（DP temp = min_left_index[temp] # 当找到左侧矮一级的目标柱子时 min_left_index[i] = temp # 记录每个柱子的右侧第一个矮一级的柱子的下标 min_right_index[size-1] = size # 初始化防止while***循环 for i in range(size-2, -1, -1): # 以当前柱子为主心骨，向右迭代寻找次级柱子 temp = i + 1 while temp = heights[i]: # 当右侧的柱子持续较高时，尝试这个高柱子自己的次级柱子（DP temp = min_right_index[temp] # 当找到右侧矮一级的目标柱子时 min_right_index[i] = temp for i in range(size): area = heights[i] * (min_right_index[i] - min_left_index[i] - 1) result = max(area, result) return result# 单调栈class Solution: def largestRectangleArea(self, heights: List[int]) -> int: # Monotonic Stack ''' 找每个柱子左右侧的第一个高度值小于该柱子的柱子 单调栈：栈顶到栈底：从大到小（每插入一个新的小数值时，都要弹出先前的大数值） 栈顶，栈顶的下一个元素，即将入栈的元素：这三个元素组成了最大面积的高度和宽度 情况一：当前遍历的元素heights[i]大于栈顶元素的情况 情况二：当前遍历的元素heights[i]等于栈顶元素的情况 情况三：当前遍历的元素heights[i]小于栈顶元素的情况 ''' # 输入数组首尾各补上一个0（与42.接雨水不同的是，本题原首尾的两个柱子可以作为核心柱进行最大面积尝试 heights.insert(0, 0) heights.append(0) stack = [0] result = 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] int: heights.insert(0, 0) heights.append(0) stack = [0] result = 0 for i in range(1, len(heights)): while stack and heights[i]