代码随想录算法训练营第58天 | 单调栈 ●739 每日温度 ●496下一个更大元素I ●503下一个更大元素II ●42 接雨水 ●84 柱形图中最大的矩形

**代码随想录算法训练营第58天**

## 单调栈系列问题###739. 每日温度给定一个整数数组 `temperatures`，返回每个元素的下一个更高温度。

#### 示例：

* 输入：`temperatures = [73,74,75,71,69,72,76,73]`
* 输出：`[1,1,4,2,1,1,0,0]`

#### 思路：

我们可以使用单调栈来解决这个问题。具体来说，我们维护一个递减的栈，用于存储温度数组中当前元素之前更高温度的下标。

####代码：

def dailyTemperatures(temperatures):
 stack = []
 result = [0] * len(temperatures)
 for i in range(len(temperatures)):
 while stack and temperatures[i] > temperatures[stack[-1]]:
 idx = stack.pop()
 result[idx] = i - idx stack.append(i)
 return result# 测试用例：
print(dailyTemperatures([73,74,75,71,69,72,76,73]))# 输出：[1,1,4,2,1,1,0,0]

###496. 下一个更大元素I给定两个整数数组 `nums1` 和 `nums2`，返回 `nums1` 中每个元素的下一个更大元素。如果不存在，则返回 `-1`。

#### 示例：

* 输入：`nums1 = [4,1,2]`, `nums2 = [1,3,4,2]`
* 输出：`[3,-1,3]`

#### 思路：

我们可以使用单调栈来解决这个问题。具体来说，我们维护一个递减的栈，用于存储 `nums1` 中当前元素之前更大元素的下标。

####代码：

def nextGreaterElement(nums1, nums2):
 stack = []
 result = {}
 for num in nums2:
 while stack and num > stack[-1]:
 result[stack.pop()] = num stack.append(num)
 return [result.get(num, -1) for num in nums1]

# 测试用例：
print(nextGreaterElement([4,1,2], [1,3,4,2]))# 输出：[3, -1,3]

###503. 下一个更大元素II给定两个整数数组 `nums1` 和 `nums2`，返回 `nums1` 中每个元素的下一个更大元素。如果不存在，则返回 `-1`。

#### 示例：

* 输入：`nums1 = [4,5,8,9]`, `nums2 = []`
* 输出：`[-1,-1,-1,-1]`

#### 思路：

我们可以使用单调栈来解决这个问题。具体来说，我们维护一个递减的栈，用于存储 `nums1` 中当前元素之前更大元素的下标。

####代码：

def nextGreaterElements(nums1, nums2):
 stack = []
 result = {}
 for num in nums2:
 while stack and num > stack[-1]:
 result[stack.pop()] = num stack.append(num)
 for num in nums1:
 if num not in result:
 i = (nums2.index(num) +1) % len(nums2)
 while stack and nums2[i] > num:
 idx = stack.pop()
 result[num] = nums2[idx]
 if idx == i: break else:
 result[num] = -1 return list(result.values())

# 测试用例：
print(nextGreaterElements([4,5,8,9], []))# 输出：[-1, -1, -1, -1]

###42. 接雨水给定一个整数数组 `height`，返回接雨水的总量。

#### 示例：

* 输入：`height = [1,8,6,2,5,4,8,3,7]`
* 输出：`49`

#### 思路：

我们可以使用单调栈来解决这个问题。具体来说，我们维护一个递增的栈，用于存储当前元素之前更高元素的下标。

####代码：

def trap(height):
 stack = []
 result =0 for i in range(len(height)):
 while stack and height[i] > height[stack[-1]]:
 h = height[stack.pop()]
 if not stack:
 break width = i - stack[-1] -1 water = min(h, height[i]) * width result += water stack.append(i)
 return result# 测试用例：
print(trap([1,8,6,2,5,4,8,3,7]))# 输出：49

###84. 柱形图中最大的矩形给定一个整数数组 `heights`，返回柱形图中最大的矩形面积。

#### 示例：

* 输入：`heights = [2,1,5,6,0,1,2,3,4]`
* 输出：`10`

#### 思路：

我们可以使用单调栈来解决这个问题。具体来说，我们维护一个递减的栈，用于存储当前元素之前更高元素的下标。

####代码：

def largestRectangleArea(heights):
 stack = []
 result =0 for i in range(len(heights)):
 while stack and heights[i] > heights[stack[-1]]:
 h = heights[stack.pop()]
 if not stack:
 break width = i - stack[-1] -1 water = min(h, heights[i]) * width result = max(result, water)
 stack.append(i)
 while stack:
 h = heights[stack.pop()]
 if not stack:
 break width = len(heights) - stack[-1] -1 water = h * width result = max(result, water)
 return result# 测试用例：
print(largestRectangleArea([2,1,5,6,0,1,2,3,4]))# 输出：10

###496. 下一个更大元素II给定两个整数数组 `nums1` 和 `nums2`，返回 `nums1` 中每个元素的下一个更大元素。如果不存在，则返回 `-1`。

#### 示例：

* 输入：`nums1 = [4,5,8,9]`, `nums2 = []`
* 输出：`[-1,-1,-1,-1]`

#### 思路：

我们可以使用单调栈来解决这个问题。具体来说，我们维护一个递减的栈，用于存储 `nums1` 中当前元素之前更大元素的下标。

####代码：

def nextGreaterElements(nums1, nums2):
 stack = []
 result = {}
 for num in nums2:
 while stack and num > stack[-1]:
 idx = stack.pop()
 result[nums1[idx]] = num stack.append(num)
 for i in range(len(nums1)):
 if nums1[i] not in result:
 j = (nums2.index(nums1[i]) +1) % len(nums2)
 while stack and nums2[j] > nums1[i]:
 idx = stack.pop()
 result[nums1[i]] = nums2[idx]
 if idx == j: break else:
 result[nums1[i]] = -1 return list(result.values())

# 测试用例：
print(nextGreaterElements([4,5,8,9], []))# 输出：[-1, -1, -1, -1]

###503. 下一个更大元素II给定两个整数数组 `nums1` 和 `nums2`，返回 `nums1` 中每个元素的下一个更大元素。如果不存在，则返回 `-1`。

#### 示例：

* 输入：`nums1 = [4,5,8,9]`, `nums2 = []`
* 输出：`[-1,-1,-1,-1]`

#### 思路：

我们可以使用单调栈来解决这个问题。具体来说，我们维护一个递减的栈，用于存储 `nums1` 中当前元素之前更大元素的下标。

####代码：

def nextGreaterElements(nums1, nums2):
 stack = []
 result = {}
 for num in nums2:
 while stack and num > stack[-1]:
 idx = stack.pop()
 result[nums1[idx]] = num stack