代码随想录 Day - 61｜#503 下一个更大元素 II｜#42 接雨水

清单

● 503.下一个更大元素II
● 42. 接雨水

LeetCode #503 下一个更大元素II

1. 题目

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

2. 思路

此处为循环数组，在 #496 下一个更大元素 I 的思路上，通过增加遍历次数（多遍历一次数组）达到最小循环数组目的

3. 代码实现

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [-1] * n
        stack = []
        for i in range(2 * n):
            while stack and nums[i % n] > nums[stack[-1]]:
                answer[stack.pop()] = nums[i % n]
            stack.append(i % n)
        return answer
1
2
3
4
5
6
7
8
9
10

LeetCode #42 接雨水

1. 题目

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

2. 思路

1. 双指针法:
   • 从左往右看时，能够接住的雨水为sum(当前侧的最高高度 - 遍历数组元素)
   • 同理，从右向左看时，接住的雨水为sum(当前侧的最高高度 - 遍历数组元素)
   • 创建 L_height / R_height 用于记录左指针和右指针遍历数组时的最高高度
   • 遍历数组，记录 sum = max( L_height[i], R_height[i]) - height[i])
2. 单调栈:
   • 当遍历元素小于栈顶元素时，入栈
   • 当遍历元素等于栈顶元素时(高度相同)，弹出当前栈顶元素，记录当前遍历元素(更新脚标)
   • 当遍历元素大于栈顶元素时，弹出当前栈顶元素， 计算接住雨水量
   • 新增一个result用于记录所有雨水量之和

3. 代码实现

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]]:
                stack.pop()
                stack.append(i)
            else:
                while stack and height[i] > height[stack[-1]]:
                    mid_height = height[stack[-1]]
                    stack.pop()
                    if stack: #确保stack不为空
                        L_height = height[stack[-1]]
                        R_height = height[i]
                        H = min(L_height, R_height) - mid_height
                        W = i - stack[-1] - 1
                        result += H * W
                stack.append(i)
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22