Rectangle¶
Table of Contents¶
- 84. Largest Rectangle in Histogram (Hard)
- 1793. Maximum Score of a Good Subarray (Hard)
- 85. Maximal Rectangle (Hard)
- 1504. Count Submatrices With All Ones (Medium)
- 42. Trapping Rain Water (Hard)
- 755. Pour Water (Medium) 👑
84. Largest Rectangle in Histogram¶
from typing import List
class LargestRectangleArea:
def monotonic_stack(self, heights: List[int]) -> int:
stack = []
res = 0
n = len(heights)
for i in range(n + 1):
h = heights[i] if i < n else 0
while stack and h < heights[stack[-1]]:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
res = max(res, height * width)
stack.append(i)
return res
if __name__ == "__main__":
sol = LargestRectangleArea()
assert sol.monotonic_stack([2, 1, 5, 6, 2, 3]) == 10
assert sol.monotonic_stack([2, 4]) == 4
1793. Maximum Score of a Good Subarray¶
85. Maximal Rectangle¶
from typing import List
class maximalRectangle:
"""
prerequisite: 84. Largest Rectangle in Histogram
"""
def monotonic_stack(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * (n + 1)
res = 0
for row in matrix:
for i in range(n):
if row[i] == "1":
heights[i] += 1
else:
heights[i] = 0
stack = [-1]
for i in range(n + 1):
while heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i - stack[-1] - 1
res = max(res, h * w)
stack.append(i)
return res
if __name__ == "__main__":
sol = maximalRectangle()
matrix = [
["1", "0", "1", "0", "0"],
["1", "0", "1", "1", "1"],
["1", "1", "1", "1", "1"],
["1", "0", "0", "1", "0"],
]
assert sol.monotonic_stack(matrix) == 6
1504. Count Submatrices With All Ones¶
42. Trapping Rain Water¶
"""
- 
<iframe width="560" height="315" src="https://www.youtube.com/embed/ZI2z5pq0TqA?si=OEYg01dbmzvmtIwZ" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
| Approach | Time | Space |
| ---------- | ---- | ----- |
| DP | O(N) | O(N) |
| Left Right | O(N) | O(1) |
| Monotonic | O(N) | O(N) |
"""
from typing import List
# DP
def trapDP(height: List[int]) -> int:
if not height:
return 0
n = len(height)
maxLeft, maxRight = [0 for _ in range(n)], [0 for _ in range(n)]
for i in range(1, n):
maxLeft[i] = max(maxLeft[i - 1], height[i - 1])
for i in range(n - 2, -1, -1):
maxRight[i] = max(maxRight[i + 1], height[i + 1])
res = 0
for i in range(n):
res += max(0, min(maxLeft[i], maxRight[i]) - height[i])
return res
# Left Right Pointers
def trapLR(height: List[int]) -> int:
if not height:
return 0
left, right = 0, len(height) - 1
maxL, maxR = height[left], height[right]
res = 0
while left < right:
if maxL < maxR:
left += 1
maxL = max(maxL, height[left])
res += maxL - height[left]
else:
right -= 1
maxR = max(maxR, height[right])
res += maxR - height[right]
return res
# Monotonic Stack
def trapStack(height: List[int]) -> int:
stack = []
total = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
top = stack.pop()
if not stack:
break
distance = i - stack[-1] - 1
bounded_height = min(height[i], height[stack[-1]]) - height[top]
total += distance * bounded_height
stack.append(i)
return total
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trapDP(height)) # 6
print(trapLR(height)) # 6
print(trapStack(height)) # 6
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution
{
public:
int trap(vector<int> &height)
{
if (height.empty())
return 0;
int res = 0;
int left = 0, right = height.size() - 1;
int maxL = height[left], maxR = height[right];
while (left < right)
{
if (maxL < maxR)
{
left++;
maxL = max(maxL, height[left]);
res += maxL - height[left];
}
else
{
right--;
maxR = max(maxR, height[right]);
res += maxR - height[right];
}
}
return res;
}
};
int main()
{
vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Solution solution;
cout << solution.trap(height) << endl;
return 0;
}