代码随想录算法训练营第六十二、六十三天 | 单调栈 part 2 | 503.下一个更大元素II 、42. 接雨水、84.柱状图中最大的矩形

503.下一个更大元素II

Leetcode

思路

将数组乘2来遍历即可，就是加长版的每日温度。

但是处理起来会有细节，如果只是单纯数组乘二，最后返回的时候还需要返回数组的一半大小，空间上不是很划算。

其实不需要扩大数组，只需要在遍历的时候，遍历长度为2*len(nums), 然后nums[i % len(nums)]即可。

代码

数组乘2

class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:nums = nums + numsres = [-1] * len(nums)stack = [0]for i in range(1, len(nums)):if nums[i] <= nums[stack[-1]]:stack.append(i)else:while stack and nums[i] > nums[stack[-1]]:res[stack[-1]] = nums[i]stack.pop()stack.append(i)return res[:len(nums)//2]

遍历长度为2*len(nums)

class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:dp = [-1] * len(nums)stack = []for i in range(len(nums)*2):while(len(stack) != 0 and nums[i%len(nums)] > nums[stack[-1]]):dp[stack[-1]] = nums[i%len(nums)]stack.pop()stack.append(i%len(nums))return dp

42. 接雨水

Leetcode

思路一 双指针

对于每一个柱子，用两个list分别存放左边最高的柱子，和右边最高的柱子。

列4 左侧最高的柱子是列3，高度为2（以下用lHeight表示）。

列4 右侧最高的柱子是列7，高度为3（以下用rHeight表示）。

列4 柱子的高度为1（以下用height表示）

那么列4的雨水高度为 列3和列7的高度最小值减列4高度，即： min(lHeight, rHeight) - height。

在有了rHeight和lHeight的情况下，遍历所以的柱子，求出雨水体积即可。

思路二 单调栈

单调栈按照行方向来计算雨水体积

代码

双指针

class Solution:def trap(self, height: List[int]) -> int:lHeight, rHeight = [0] * len(height), [0] * len(height)lHeight[0] = height[0]for i in range(1, len(lHeight)):# 计算左边最高柱子的时候连自己也包括lHeight[i] = max(lHeight[i - 1], height[i])rHeight[-1] = height[-1]for i in range(len(rHeight) - 2, -1, -1):rHeight[i] = max(rHeight[i + 1], height[i])res = 0for i in range(len(height)):res += (min(rHeight[i], lHeight[i]) - height[i])return res

单调栈

class Solution:def trap(self, height: List[int]) -> int:stack = [0]result = 0for 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]# 雨水宽度是 凹槽右侧的下标 - 凹槽左侧的下标 - 1w = i - stack[-1] - 1# 累计总雨水体积result += h * wstack.append(i)return result

84.柱状图中最大的矩形

Leetcode

思路一 双指针

对于每一个柱子，用两个list分别存放左边第一个小于该柱子的下标，和右边第一个小于该柱子的下标。

在有两个list的基础上，遍历heights,

res += heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1)

思路二 单调栈

思路来源：neetcode

代码

单调栈

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:maxArea = 0stack = []for i, h in enumerate(heights):start = iwhile stack and stack[-1][1] > h:index, height = stack.pop()maxArea = max(maxArea, height * (i - index))start = indexstack.append([start, h])for i, h in stack:maxArea = max(maxArea, h * (len(heights) - i))return maxArea