代码随想录算法训练营第六十二、六十三天 | 单调栈 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 + nums
        res = [-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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

遍历长度为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
1
2
3
4
5
6
7
8
9
10

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 = 0
        for i in range(len(height)):
            res += (min(rHeight[i], lHeight[i]) - height[i])

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

单调栈

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = [0]
        result = 0
        for 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]
                    # 雨水宽度是 凹槽右侧的下标 - 凹槽左侧的下标 - 1
                    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

84.柱状图中最大的矩形

Leetcode

思路一 双指针

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

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

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

思路二 单调栈

思路来源：neetcode

代码

单调栈

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxArea = 0
        stack = []

        for i, h in enumerate(heights):
            start = i
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                maxArea = max(maxArea, height * (i - index))
                start = index
            stack.append([start, h])
        
        for i, h in stack:
            maxArea = max(maxArea, h * (len(heights) - i))
        
        return maxArea
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17