1

# 經典題- 84. Largest Rectangle in Histogram

Monotone Stack中最經典的一道題大概屬這道吧，

python程式碼:

``````class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
"""
計算直方圖的最大面積
"""
res = 0
stack = [-1] # 較特別，存的是index而不是直接存高度，因為要留存寬度訊息。trick放入index「-1」
heights.append(0) # trick: 在陣列尾巴放一個0以把stack內元素拋出
for i in range(len(heights)):
while stack[-1]!=-1 and heights[stack[-1]] >= heights[i]:
cur = stack.pop()
res = max(res, heights[cur] * (i-stack[-1]-1))
stack.append(i)
return res
``````

• stack存的是index而不是直接存高度，因為要留存寬度訊息。
• stack一開始放入index「-1」，方便直接計算寬度
• heights一定都是正整數，尾巴多放一個0以把stack內元素拋出

input:

index - 0 1 2 3 4

# Hard- 85. Maximal Rectangle

``````["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]

would become
[1, 0, 1, 0, 0],
[2, 0, 2, 1, 1],
[3, 1, 3, 2, 2],
[4, 0, 0, 3, 0]
``````

``````def largestRectangleArea(heights):
"""
計算直方圖的最大面積
"""
res = 0
stack = [-1] # 較特別，存的是index而不是直接存高度，因為要留存寬度訊息。trick放入index「-1」
heights.append(0) # trick: 在陣列尾巴放一個0以把stack內元素拋出
for i in range(len(heights)):
while stack[-1]!=-1 and heights[stack[-1]] >= heights[i]:
cur = stack.pop()
res = max(res, heights[cur] * (i-stack[-1]-1))
stack.append(i)
return res

def store_continuous(matrix):
for c in range(len(matrix[0])):
freq = 0
for r in range(len(matrix)):
if matrix[r][c] == "1":
freq += 1
matrix[r][c] = freq
else:
matrix[r][c] = 0
freq = 0

class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not (matrix and matrix[0]):
return 0
store_continuous(matrix)
return max([largestRectangleArea(row) for row in matrix])

``````

# Medium- 907. Sum of Subarray Minimums

``````class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
res = 0
stack = [-1] # 較特別，存的是index而不是直接存高度，因為要留存寬度訊息。trick放入index「-1」
heights = arr+[0] # trick: 在陣列尾巴放一個0以把stack內元素拋出
for i in range(len(heights)):
while stack[-1]!=-1 and heights[stack[-1]] >= heights[i]:
cur = stack.pop()
res += heights[cur]*(i-cur)*(cur-stack[-1])
stack.append(i)
return res%(10**9+7)
``````

# Hard- 1793. Maximum Score of a Good Subarray

``````class Solution:
def maximumScore(self, nums: List[int], k: int) -> int:
"""
本題思路其實與84. Largest Rectangle in Histogram一樣，
差別在只有跨越nums[k]的矩形需要被計算最大值
"""
res = 0
stack = [-1] # 較特別，存的是index而不是直接存高度，因為要留存寬度訊息。trick放入index「-1」
heights = nums+[0] # trick: 在陣列尾巴放一個0以把stack內元素拋出
for i in range(len(heights)):
while stack[-1]!=-1 and heights[stack[-1]] >= heights[i]:
cur = stack.pop()
if stack[-1]<k<i:
res = max(res, heights[cur] * (i-stack[-1]-1))
stack.append(i)
return res
``````

# Medium- 1856. Maximum Subarray Min-Product

`res = max(res, nums[cur] * (accum_sum[i]-accum_sum[stack[-1]+1]))`即可

``````from itertools import accumulate
class Solution:
def maxSumMinProduct(self, nums: List[int]) -> int:
res = 0
stack = [-1] # 較特別，存的是index而不是直接存高度，因為要留存寬度訊息。trick放入index「-1」
heights = nums +[0] # trick: 在陣列尾巴放一個0以把stack內元素拋出
accum_sum = list(accumulate(nums, initial=0))
for i in range(len(heights)):
while stack[-1]!=-1 and heights[stack[-1]] >= heights[i]:
cur = stack.pop()
res = max(res, nums[cur] * (accum_sum[i]-accum_sum[stack[-1]+1]))
stack.append(i)
return res%(10**9+7)
``````