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¶
from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
"""Two Pointers: O(n) time, O(1) space.
Track max from each side; shorter side determines water level.
"""
left, right = 0, len(height) - 1
max_l = max_r = res = 0
while left < right:
if height[left] < height[right]:
max_l = max(max_l, height[left])
res += max_l - height[left]
left += 1
else:
max_r = max(max_r, height[right])
res += max_r - height[right]
right -= 1
return res
def trapDP(self, height: List[int]) -> int:
"""DP Prefix Max: O(n) time, O(n) space.
Precompute max heights from left and right.
"""
n = len(height)
max_left = [0] * n
max_right = [0] * n
for i in range(1, n):
max_left[i] = max(max_left[i - 1], height[i - 1])
for i in range(n - 2, -1, -1):
max_right[i] = max(max_right[i + 1], height[i + 1])
return sum(max(0, min(max_left[i], max_right[i]) - height[i]) for i in range(n))
def trapStack(self, height: List[int]) -> int:
"""Monotonic Stack: O(n) time, O(n) space.
Pop shorter bars and accumulate trapped water by layer.
"""
stack = []
res = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
top = stack.pop()
if not stack:
break
w = i - stack[-1] - 1
h = min(height[i], height[stack[-1]]) - height[top]
res += w * h
stack.append(i)
return res
def test_trap():
s = Solution()
for fn in (s.trap, s.trapDP, s.trapStack):
assert fn([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
assert fn([4, 2, 0, 3, 2, 5]) == 9
assert fn([1, 0, 1]) == 1
assert fn([]) == 0
#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;
}