代码随想训练营第五十九天（Python）｜ 503.下一个更大元素II、42. 接雨水

[503.下一个更大元素II]
循环问题用 2*n , i % n 的方式

        n = len(nums)
        ans = [-1] * n
        stack = []
        for i in range(2 * n):
            while len(stack) > 0 and nums[i % n] > nums[stack[-1]]:
                ans[stack[-1]] = nums[i % n]
                stack.pop()
            stack.append(i % n)
        return ans

[42. 接雨水]
1、双指针
注意点： 按列计算，找出左右的最大值

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) <= 2:
            return 0
        n = len(height)
        l_max_h, r_max_h = [0] * n, [0] * n
        l_max_h[0], r_max_h[n-1] = height[0], height[n-1]
        for i in range(1, n):
            l_max_h[i] = max(height[i], l_max_h[i-1])
        for j in range(n-2, -1, -1):
            r_max_h[j] = max(height[j], r_max_h[j+1])
        sum1 = 0
        for k in range(1, n-1):
            cur_h = min(l_max_h[k], r_max_h[k]) - height[k]
            if cur_h > 0:
                sum1 += cur_h
        return sum1

2、单调栈

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        # 单调递减栈
        stack = []
        ans = 0
        for i in range(n):
            while len(stack) > 0 and height[i] > height[stack[-1]]:
                mid = stack.pop()
                if len(stack) > 0:
                    h = min(height[stack[-1]], height[i]) - height[mid]
                    w = i - stack[-1] - 1
                    ans += h * w
            stack.append(i)
        return ans