Day 59 單調(diào)棧：503. 下一個更大元素 II, 42. 接雨水，407. 接雨水 II，11. 盛最多水的容器, 84. 柱狀圖中最大的矩形

503. 下一個更大元素 II

  • 思路
    • example
    • 循環(huán)數(shù)組
      • [1, 2, 1, 1, 2, 1]
      • 遍歷兩倍大小的數(shù)組（取模運算），按照常規(guī)數(shù)組操作，最后返回size n的結(jié)果數(shù)組即可。
        • 可能會有重復操作，但是方便。
  • 復雜度. 時間：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. 接雨水

  • 思路

  • 復雜度. 時間：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

  • 單調(diào)棧 ( 橫向接水）


class Solution:
    def trap(self, height: List[int]) -> int:
        # 單調(diào)棧
        '''
        單調(diào)棧是按照 行 的方向來計算雨水
        從棧頂?shù)綏５椎捻樞颍簭男〉酱?        通過三個元素來接水：棧頂，棧頂?shù)南乱粋€元素，以及即將入棧的元素
        雨水高度是 min(凹槽左邊高度, 凹槽右邊高度) - 凹槽底部高度
        雨水的寬度是 凹槽右邊的下標 - 凹槽左邊的下標 - 1（因為只求中間寬度）
        '''
        # stack儲存index，用于計算對應的柱子高度
        stack = [0]
        result = 0
        for i in range(1, len(height)):
            # 情況一
            if height[i] < height[stack[-1]]:
                stack.append(i)

            # 情況二
            # 當當前柱子高度和棧頂一致時，左邊的一個是不可能存放雨水的，所以保留右側(cè)新柱子
            # 需要使用最右邊的柱子來計算寬度
            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]]
                        # 兩側(cè)的較矮一方的高度 - 凹槽底部高度
                        h = min(right_height, left_height) - mid_height
                        # 凹槽右側(cè)下標 - 凹槽左側(cè)下標 - 1: 只求中間寬度
                        w = i - stack[-1] - 1
                        # 體積：高乘寬
                        result += h * w
                stack.append(i)
        return result

407. 接雨水 II

  • 思路
    • example
    • 接雨水 高維版本
    • 由外身內(nèi)遍歷邊界 （水一定是從外邊界溢出）
      • 優(yōu)先隊列 （最小堆 heapq）
      • directions方向向量: 方便考察最小邊界周圍點的水位
      • visited數(shù)組避免重復訪問
        • 判斷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]結(jié)果后，考慮left += 1, 或者right -= 1
    • 如果height[left] < height[right]: 考慮left += 1, 這樣在寬度減小的情況下，min_height有可能增大；否則如果right-=1, min_height <= height[left]，不可能改進結(jié)果。(height[left] < height[right]的情況下，區(qū)間[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)
    • 單調(diào)棧
    • 復雜度. 時間：O(n), 空間: O(n) 
TBA
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容