Day 59 单调栈：503. 下一个更大元素 II, 42. 接雨水，407. 接雨水 II，11. 盛最多水的容器, 84. 柱状图中最大的矩形

503. 下一个更大元素 II

思路
- example
- 循环数组
  - [1, 2, 1, 1, 2, 1]
  - 遍历两倍大小的数组（取模运算），按照常规数组操作，最后返回size n的结果数组即可。
    - 可能会有重复操作，但是方便。
复杂度. 时间：O(n), 空间: O(n)

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

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)  
        res = [-1 for _ in range(n)] 
        stack = [] 
        for i in range(2*n):
            if not stack or nums[stack[-1]] >= nums[i%n]:
                stack.append(i%n) 
            else: 
                while stack and nums[stack[-1]] < nums[i%n]:
                    idx = stack.pop()  
                    res[idx] = nums[i%n] 
                stack.append(i%n) 
        return res

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        nums1 = nums + nums 
        n = len(nums1) 
        res = [-1 for _ in range(len(nums1))] 
        stack = [0] 
        for i in range(1, n):
            while stack and nums1[i] > nums1[stack[-1]]:
                idx = stack.pop()
                res[idx] = nums1[i] 
            stack.append(i) 
        return res[:n//2]

42. 接雨水

思路
- example
- 暴力（双指针，中心扩散法），DP (两次遍历）, 双指针，优先队列: https://www.jianshu.com/p/538520fed566
  - 纵向接水
复杂度. 时间：O(n), 空间: O(n)

# DP
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        leftMax = [0 for _ in range(n)]
        rightMax = [0 for _ in range(n)]
        for i in range(1, n):
            leftMax[i] = max(leftMax[i-1], height[i-1])
        for i in range(n-2, -1, -1):
            rightMax[i] = max(rightMax[i+1], height[i+1])
        res = 0
        for i in range(n):
            h = min(leftMax[i], rightMax[i])
            res += max(0, h-height[i])
        return res

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height) 
        leftMax = [0 for _ in range(n)] 
        rightMax = [0 for _ in range(n)] 
        for i in range(1, n):
            leftMax[i] = max(leftMax[i-1], height[i-1]) 
        for i in range(n-2, -1, -1):
            rightMax[i] = max(rightMax[i+1], height[i+1])  
        res = 0 
        for i in range(n):
            res += max(min(leftMax[i], rightMax[i])-height[i], 0)
        return res

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height) 
        left = [0 for _ in range(n)]
        right = [0 for _ in range(n)] 
        for i in range(1, n):
            left[i] = max(left[i-1], height[i-1]) 
        for j in range(n-2, -1, -1):
            right[j] = max(right[j+1], height[j+1]) 
        res = 0 
        for i in range(n):
            res += max(min(left[i], right[i]) - height[i], 0) # !!!
        return res

单调栈 ( 横向接水）

class Solution:
    def trap(self, height: List[int]) -> int:
        # 单调栈
        '''
        单调栈是按照 行 的方向来计算雨水
        从栈顶到栈底的顺序：从小到大
        通过三个元素来接水：栈顶，栈顶的下一个元素，以及即将入栈的元素
        雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度
        雨水的宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度）
        '''
        # stack储存index，用于计算对应的柱子高度
        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:
                        right_height = height[i]
                        left_height = height[stack[-1]]
                        # 两侧的较矮一方的高度 - 凹槽底部高度
                        h = min(right_height, left_height) - mid_height
                        # 凹槽右侧下标 - 凹槽左侧下标 - 1: 只求中间宽度
                        w = i - stack[-1] - 1
                        # 体积：高乘宽
                        result += h * w
                stack.append(i)
        return result

407. 接雨水 II

思路
- example
- 接雨水高维版本
- 由外身内遍历边界（水一定是从外边界溢出）
  - 优先队列（最小堆 heapq）
  - directions方向向量: 方便考察最小边界周围点的水位
  - visited数组避免重复访问
    - 判断visited[x][y]时先检查x,y是否越界。
- 复杂度. 时间： $O(mn)$ , 空间: $O(m+n)$

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        m, n = len(heightMap), len(heightMap[0])
        if m <= 2 or n <= 2:
            return 0  
        que = []
        visited = [[False for _ in range(n)] for _ in range(m)]
        for j in range(n):
            heapq.heappush(que, (heightMap[0][j], (0,j)))
            visited[0][j] = True
            heapq.heappush(que, (heightMap[m-1][j], (m-1,j)))  
            visited[m-1][j] = True 
        for i in range(1, m-1):
            heapq.heappush(que, (heightMap[i][0], (i,0)))
            visited[i][0] = True 
            heapq.heappush(que, (heightMap[i][n-1], (i,n-1)))
            visited[i][n-1] = True 
        res = 0
        directions = [(0,1), (0,-1), (-1,0), (1,0)]
        while que:  
            h, position = heapq.heappop(que) 
            x0, y0 = position[0], position[1]
            for direction in directions:
                x, y = x0 + direction[0], y0 + direction[1]
                if 0<=x<m and 0<=y<n and visited[x][y] == False: 
                    h_new = max(h, heightMap[x][y])
                    res += h_new - heightMap[x][y]
                    heapq.heappush(que, (h_new, (x,y)))
                    visited[x][y] = True 
        return res

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        m, n = len(heightMap), len(heightMap[0]) 
        if m<=2 or n <=2:
            return 0 
        que = [] 
        visited = [[False for _ in range(n)] for _ in range(m)]
        for j in range(n):
            heapq.heappush(que, (heightMap[0][j], (0,j))) 
            heapq.heappush(que, (heightMap[m-1][j], (m-1,j))) 
            visited[0][j] = True 
            visited[m-1][j] = True 
        for i in range(1, m-1):
            heapq.heappush(que, (heightMap[i][0], (i,0)))
            heapq.heappush(que, (heightMap[i][n-1], (i,n-1)))
            visited[i][0] = True 
            visited[i][n-1] = True  
        directions = [(0,1), (1,0), (-1,0), (0,-1)]
        res = 0  
        while que:
            h, pos = heapq.heappop(que)
            x0, y0 = pos[0], pos[1] 
            for direction in directions:
                x, y = x0+direction[0], y0+direction[1]
                if x >=0 and x<m and y>=0 and y<n:
                    if visited[x][y]:
                        continue  
                    new_h = max(h, heightMap[x][y]) 
                    res += max(0, new_h - heightMap[x][y]) 
                    heapq.heappush(que, (new_h, (x,y))) 
                    visited[x][y] = True  
        return res

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        m, n = len(heightMap), len(heightMap[0]) 
        visit = [[False for _ in range(n)] for _ in range(m)] 
        que = []
        for j in range(n):
            visit[0][j] = True 
            visit[m-1][j] = True
            heapq.heappush(que, (heightMap[0][j], (0, j)))
            heapq.heappush(que, (heightMap[m-1][j], (m-1, j)))
        for i in range(m):
            visit[i][0] = True 
            visit[i][n-1] = True 
            heapq.heappush(que, (heightMap[i][0], (i, 0)))
            heapq.heappush(que, (heightMap[i][n-1], (i, n-1)))
        directions = [(-1,0), (1,0), (0,1), (0,-1)]
        res = 0
        while que:
            height, pos = heapq.heappop(que) 
            x0, y0 = pos[0], pos[1] 
            for i in range(4):
                x, y = x0+directions[i][0], y0+directions[i][1]
                if x >= 0 and x < m and y >=0 and y < n and visit[x][y] == False:
                    res += max(0, height - heightMap[x][y]) 
                    if height > heightMap[x][y]:
                        waterlevel = height 
                    else:
                        waterlevel = heightMap[x][y]
                    heapq.heappush(que, (waterlevel, (x,y)))
                    visit[x][y] = True # !!!
        return res

11. 盛最多水的容器

思路
- example
- 短板效应
  - [left, right]: 储水量 = min(height[left], height[right]) * (right - left)
- 解法1：暴办法
  - 复杂度. 时间： $O(n^2)$ , 空间: $O(1)$

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        res = 0
        for left in range(n):
            for right in range(left+1, n):
                res = max(res, min(height[left], height[right]) * (right - left))
        return res

解法2：双指针， -->*<--
- left, right = 0, n-1
- 在更新完[left, right]结果后，考虑left += 1, 或者right -= 1
- 如果height[left] < height[right]: 考虑left += 1, 这样在宽度减小的情况下，min_height有可能增大；否则如果right-=1, min_height <= height[left]，不可能改进结果。(height[left] < height[right]的情况下，区间[left, j] where j < right不需要考虑了。)
- 复杂度. 时间： $O(n)$ , 空间: $O(1)$

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        left, right = 0, n-1
        res = 0
        while left < right:
            res = max(res, min(height[left], height[right])*(right-left))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return res

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height) 
        left, right = 0, n-1  
        res = 0 
        while left < right:
            res = max(res, min(height[left], height[right])*(right-left))
            if height[left] < height[right]:
                left += 1 
            else:
                right -= 1
        return res

84. 柱状图中最大的矩形

思路
- example
- 暴力双指针（中心扩散）: $O(n^2)$
- 单调栈
- 复杂度. 时间： $O(n)$ , 空间: $O(n)$

TBA

最后编辑于：2024.02.29 04:48:37

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,189评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,577评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,857评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,703评论 1赞 276
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,705评论 5赞 366
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,620评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,995评论 3赞 396
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,656评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,898评论 1赞 298
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,639评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,720评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,395评论 4赞 319
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,982评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,953评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,195评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 44,907评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,472评论 2赞 342

Day 59 单调栈：503. 下一个更大元素 II, 42. 接雨水，407. 接雨水 II，11. 盛最多水的容器, 84. 柱状图中最大的矩形

503. 下一个更大元素 II

42. 接雨水

407. 接雨水 II

11. 盛最多水的容器

84. 柱状图中最大的矩形

推荐阅读更多精彩内容