代码随想录 单调栈part2

503. 下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

思路：在后面多续一段

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. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水

思路：

1. 双指针（dp）：从列的角度去看，每一列可以装的雨水取决于左边最高的柱子和右边最高的柱子和该列的高度的差。可以使用双指针，当前列的左边最高的柱子可以由前一列的左边最高柱子转移而来，同理列的右边最高的柱子可以由后一列的左边最高柱子转移而来。

class Solution:
    def trap(self, height: List[int]) -> int:
        left_dp = [0 for _ in range(len(height))]  # 记录左边最高的柱子
 
        right_dp = [0 for _ in range(len(height))]  # 记录右边最高的柱子
 
        ans = 0
        left_max= 0
        right_max = 0
        for i in range(1, len(height)):  # 求每一列左边最高的柱子
            left_dp[i] = max(left_dp[i-1], height[i-1])
        
        for j in range(len(height) -2 , 0, -1):  # 求每一列右边最高的柱子
            right_dp[j] = max(right_dp[j+1], height[j+1])
        
        for k in range(len(height)):  # 求可以接住的雨水
            h = min(left_dp[k], right_dp[k]) - height[k]
            ans += max(0, h)
 
        return ans

2. 单调栈

从行的角度去看，需要找到一个个凹槽，大的凹槽又有小凹槽，可以将凹槽都归一为底部平坦的凹槽，如果有小凹槽，再计算小凹槽的积水量后，就认为其填上了，这样每一个凹槽都是底部平坦的凹槽，凹槽积水量就是 雨水高度 * 雨水深度，其中雨水高度为min(凹槽左侧高度, 凹槽右侧高度) - 凹槽底部高度，雨水宽度是 凹槽右侧的下标 - 凹槽左侧的下标 - 1。找的是该元素左边和右边第一个大于该元素的位置和高度，可以用单调栈。

单调栈性质，从栈头到栈尾单调递增，当遇到比栈头元素大的就是出现凹槽，计算凹槽的雨水体积。

class Solution:
    def trap(self, height: List[int]) -> int:
   
        stack = [0]
        result = 0
        for i in range(1, len(height)):
         
            if height[i] < height[stack[-1]]:
                stack.append(i)
 
        
            # 当当前柱子高度和栈顶一致时，只需要保存一个柱子，作为凹槽底部高度的记录
            elif height[i] == height[stack[-1]]:
                continue
    
            else:
                while stack and 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
                        w = i - stack[-1] - 1
                       
                        result += h * w
                stack.append(i)
        return result